以下模板代码的字符串下标均从1开始。
当遇到性能问题时很可能是vector导致的，换成普通数组也可以。
字符串 (s) 的前缀函数 (pi[i]) 表示长度为 (i) 的前缀中最长的公共前后缀的长度。
kmp 找出模式字符串 (t) 在文本字符串 (s) 中出现的所有的位置。
namespace KnuthMorrisPrattAlgorithm {
vi getPi(char *s) {
int slen = strlen(s + 1);
vi pi(slen + 1);
for(int i = 2, j = 0; i <= slen; ++i) {
for(; j && s[i] != s[j + 1]; j = pi[j]);
j += (s[i] == s[j + 1]);
pi[i] = j;
}
return pi;
}
vi kmp(char *s, char *t) {
int slen = strlen(s + 1), tlen = strlen(t + 1);
vi pi = getPi(t), res;
for(int i = 1, j = 0; i <= slen; ++i) {
for(; j && s[i] != t[j + 1]; j = pi[j]);
j += (s[i] == t[j + 1]);
if(j == tlen)
res.pb(i - tlen + 1);
}
return res;
}
}
字符串 (s) 的z函数 (z[i]) 表示以 (i) 位置为左端点的后缀中，与字符串 (s) 的最长的公共前缀的长度。
exkmp：找出从(s[i])开始的，和模式串 (t) 的最长公共前缀。
namespace ExtendKnuthMorrisPrattAlgorithm {
vi getZ(char *s, int n) {
vi z(n + 1);
z[1] = n;
for(int i = 2, l = 0, r = 0; i <= n; ++i) {
if(i <= r)
z[i] = min(z[i - l + 1], r - i + 1);
for(; i + z[i] <= n && s[i + z[i]] == s[z[i] + 1]; ++z[i]);
if(i + z[i] - 1 > r)
l = i, r = i + z[i] - 1;
}
return z;
}
vi exkmp(char *s, char *t) {
int n = strlen(s + 1), m = strlen(t + 1);
vi z = getZ(t, m), res(n + 1);
for(int i = 1, l = 0, r = 0; i <= n; ++i) {
if(i <= r)
res[i] = min(z[i - l + 1], r - i + 1);
for(; i + res[i] <= n && s[i + res[i]] == t[res[i] + 1]; ++res[i]);
if(i + res[i] - 1 > r)
l = i, r = i + res[i] - 1;
}
return res;
}
}
统计既是字符串 (s) 的前缀又是字符串 (s) 的后缀的所有字符串的长度及其出现次数：易知 (z[i]=(n+1-i)) 表示后缀字符串 (s[i,n]) 与字符串 (s) 的最长公共前缀的长度等于后缀字符串 (s[i,n]) 的长度，所以后缀字符串 (s[i,n]) 满足既是字符串 (s) 的前缀又是字符串 (s) 的后缀，且其长度为 (z[i]) 。那么它的出现次数可以直接用dp求出来（长度为 (z[i]+1) 的字符串出现，则长度为 (z[i]) 的字符串也出现）。
上面这些函数存在越界访问的现象，在对字符串使用时由于字符串末尾一定是特殊字符所以没事，但是对整数数组进行匹配时要小心。