$$ 1. 子串查找 $$

#include<cstdio>
#include<cstring>

using namespace std;

const int N = 1e6 + 1;

int an, bn, ans, f[N], j;
char a[N], b[N];

int main()
{
    scanf("%s", a + 1);
    scanf("%s", b + 1);

    an = strlen(a + 1);
    bn = strlen(b + 1);

    j = 0;
    for(int i = 2;i <= bn;i ++){
        while(j && b[i] != b[j + 1]) j = f[j];
        if(b[i] == b[j + 1]) j ++;
        f[i] = j;
    }

    j = 0;
    for(int i = 1;i <= an;i ++){
        while(j && a[i] != b[j + 1]) j = f[j];
        if(a[i] == b[j + 1]) j ++;
        if(j == bn)
        ans ++;
    }

    printf("%d", ans);

    return 0;
}

$$ 2. 重复子串 $$

#include<cstdio>
#include<cstring>

using namespace std;

const int N = 1e6 + 1;

int len, ans, ne[N], j;
char a[N];

int main()
{
    scanf("%s", a + 1);
    len = strlen(a + 1);

    while(len != 1 || a[1] != '.')
    {
        j = 0;
        for(int i = 2;i <= len;i ++)
        {
            while(j && a[i] != a[j + 1]) j = ne[j];
            if(a[i] == a[j + 1]) j ++;
            ne[i] = j;
        }
        if(len % (len - ne[len]) == 0)
            printf("%d\n", len / (len - ne[len]));
        else
            puts("1\n");
        scanf("%s",a + 1);
        len = strlen(a + 1);
    }
    return 0;
}

$$ 3. 周期长度和 $$

#include<cstdio>
#include<cstring>

using namespace std;

const int N = 1e6 + 1;
typedef long long ll;

int n, j;
int  p[N];
char a[N];

ll ans;

inline int find(int x){
    if(p[x] != 0)
        return p[x] = find(p[x]);
    return x;
}

int main(){
    scanf("%d",&n);
    scanf("%s",a + 1);

    j = 0;
    for(int i = 2;i <= n;i ++){
        while(j && a[i] != a[j + 1]) j = p[j];
        if(a[i] == a[j + 1]) j ++;
        p[i] = j;
    }

    for(int i = 1;i <= n;i ++)
        ans += i - find(i);

    printf("%lld",ans);

    return 0;
}

$$ 4. 子串拆分 $$

#include<cstdio>
#include<cstring>

using namespace std;

const int N = 1.5e4 + 1;
typedef long long ll;

int len, len2;
ll ans = 0;
int p[N], j, K;
char a[N], now[N];

int main()
{
    scanf("%s",a + 1);
    scanf("%d",&K);

    len = strlen(a + 1);

    for(register int i = 1;i <= len;i ++){

        memset(now, 0 ,sizeof(now));
        for(int k = 1;i + k - 1 <= len;k ++)
            now[k] = a[i + k - 1];
        memset(p, 0, sizeof(p));
        len2 = strlen(now + 1);

    j = 0;
    for(register int i = 2;i <= len2;i ++)
    {
        while(j && now[i] != now[j + 1]) j = p[j];
        if(now[i] == now[j + 1]) j ++;
        p[i] = j;
    }   

    j = 0;
    for(register int i = 1;i <= len2;i ++)
    {
        while(j && now[i] != now[j + 1]) j = p[j];
        if(now[i] == now[j + 1]) j ++;
        while((j << 1) >= (i))  j = p[j];
        if(j >= K) ++ ans;
    }
}   
    printf("%lld", ans);

    return 0;
}