KMP

实现方法有很多，简单介绍一种

ababababab
0012345678

abababa
abababa
ababa
ababa
aba
aba
a
a

ababababcdddddd
ababababab
0012345678
ababababab

abacabadabacaba
001012301234567

abacabadabacabad
0010123012345678

abacabadabacabac
0010123012345674

abacabadabacabab
0010123012345672

abacabadabacabaa
0010123012345671

abacabadabacabae
0010123012345670

对于每个前缀 s[1..i]
找到最长的前缀等于后缀的长度p[i]（不能是整个前缀
p[i] < i
s[1..p[i]] == s[i-p[i]+1..i]
长度为p[i]的前缀以i结尾长度为p[i]的后缀
最长的是p[i]
如果希望找到所有合法的解
p[i]
p[p[i]]
p[p[p[i]]]
....
直到0

一些人的定义/实现，在求p[i]时，不仅要求
s[1..p[i]] == s[i-p[i]+1..i]
还要求s[p[i]+1] != s[i]
这是没有必要的，我们不采用这种写法

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaab
aaaaaaaaab
aaaaaaaaab

abcabcabcabcabcabc
abcabcabc
abcabcabc
abcabcabc
abcabcabc
abcabcabc
abcabcabc

参考代码

#include <bits/stdc++.h>
using namespace std;
char s[1000020];
char t[1000020];
int p[1000020];
int main() {
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    int n = strlen(s + 1);
    int m = strlen(t + 1);
    int u = 0;
    for (int i = 2; i <= m; i++) {
        while (u > 0 && t[u + 1] != t[i]) {
            u = p[u];
        }
        if (t[u + 1] == t[i]) {
            u++;
        }
        p[i] = u;
    }
    u = 0;
    for (int i = 1; i <= n; i++) {
        while (u > 0 && t[u + 1] != s[i]) {
            u = p[u];
        }
        if (t[u + 1] == s[i]) {
            u++;
        }
        if (u == m) {
            printf("%d\n", i - m + 1);
            u = p[u]; // 找到的匹配允许有重叠
            // u = 0; // 找到的匹配不允许有重叠
        }
    }
    for (int i = 1; i <= m; i++) {
        printf("%d%c", p[i], i == m ? '\n' : ' ');
    }
}

P4391

cabcabca
00012345
bca
bca
ca

P3435

寻找最长的周期
不能是整个串本身

babababa 6
bababa

bababab 6
bababa

bababa 4
baba

babab 4
baba

baba 2
ba

bab 2
ba

ba 0
ba

b 0

#include <bits/stdc++.h>
using namespace std;
char s[1000020];
int p[1000020];
int f[1000020];
int n;
long long z;
int main() {
	scanf("%d", &n);
	scanf("%s", s + 1);
	int u = 0;
	f[1] = 1;
	for (int i = 2; i <= n; i++) {
		while (u > 0 && s[u + 1] != s[i]) {
			u = p[u];
		}
		if (s[u + 1] == s[i]) {
			u++;
		}
		p[i] = u;
		f[i] = i;
		if (p[i] > 0)
		{
			f[i] = f[p[i]];
		}
		z += i - f[i];
	}
	printf("%lld\n", z);
	return 0;
}