扩展KMP（Z函数）
Z数组
简单理解
\(Z[i]\) 表示字符串从i出发，与整体相比有多长的公共前缀
a a a b a a c
7 2 1 0 2 1 0
可以先理解马拉车再来看
首先，设置两个类似的东西，关键点 \(c\) 和最右边界 \(r\) ，表示 \(Z[c]\) 是目前所有 \(Z\) 中，\(i+Z[i]\) 最右边的那个
对于：
r
0 1 2 3 4 5 |
15 16 17 18 19 20 | 21 22
假定 Z[15]=6,Z[3]=3，此时c=15，r=20
现在的 \(i\) 到达18，那么通过Z数组知道 \(s[18]==s[3]\)
由于 \(Z[15]\)，则0=15,1=16,2=17,3=18,4=19,5=20
由于 \(Z[3]\)，则0=3,1=4,2=5
所以0=18,1=19,2=20，\(Z[18]=3\)
类似马拉车的 \(2*i-1\)，这里相当于 \(Z[18]=Z[18-c]\)
理解了以上部分，接下来开始细节分类
细节分类
参考左程云，他讲的巨详细
-
i没有被r包住，那么以i为出发点直接扩展
- 这个就正常比较
-
i被r包住，但是前点 i-c 的扩展长度，对应在大扩展区域以内，直接确定z[i] = z[i-c]
-
i被r包住，但是前点 i-c 的扩展长度，对应在大扩展区域的边界，从r之外的位置进行扩展
- 这个情况和上面举得例子一样，我们只知道\(s[20]=s[5]=s[2]\) ，但是不知道\(s[21]\)的信息
-
i被r包住，但是前点 i-c 的扩展长度，对应在大扩展区域以外，直接确定z[i] = r - i
- 这个看似可以像第三点那样拓展，实际上已经确定
- 还是上面的例子，只有\(Z[3]\) 改成5，则0=3,1=4,2=5,3=6,4=7
- 在\(Z[15]=6\)的情况下，\(s[21]!=s[6]=>s[21]!=s[3]=>Z[15]=min(Z[i-c],r-i)\)
这一part结束！
CODE
如下，先通过rc来获取最小答案
然后while能处理1、3情况，向外拓展，会直接跳出24情况，因为现实状况就是再外扩是不同的
z[0] = n;
for (int i = 1, c = 1, r = 1, len; i < n; i++) {
// r没包住i，设置0
// 如果包住了，那么i到右边界和关键点c的扩充长度
len = r > i ? min(r - i, z[i - c]) : 0;
// len现在是最小的长度，现在再看看能不能扩的更远
while (i + len < n && s[i + len] == s[len]) len++;
if (i + len > r) {
r = i + len;
c = i;
}
z[i] = len;
}
e数组
对于字符串A B
\(e[i]\) 表示 \(A[i\cdots n]\) 和 \(B\) 的最长前缀
假定 e[15]=6,z[3]=3，此时c=15，r=20
B:0 1 2 3 4 5
A:15 16 17 18 19 20
根据 \(e[15]\)，有：\(A[15]=B[0],A[16]=B[1],A[17]=B[2],A[18]=B[3]\)
根据 \(z[3]\)，有：\(B[0]=B[3],B[1]=B[4],B[2]=B[5]\)
有：\(A[18]=B[0],A[19]=B[1],A[20]=B[2]\)
简单说就是 \(e[i]=z[i-c]\)
// a[i...] 与 b[0...]的最长公共前缀
void eArray(string &a, string &b, int n, int m) {
for (int i = 0, c = 0, r = 0, len; i < n; i++) {
// r没包住i，设置0
// 如果包住了，那么i到右边界和关键点c的扩充长度
len = r > i ? min(r - i, z[i - c]) : 0;
// len现在是最小的长度，现在再看看能不能扩的更远
while (i + len < n && len < m && a[i + len] == b[len]) len++;
if (i + len > r) {
r = i + len;
c = i;
}
e[i] = len;
}
}