扩展KMP（Z algorithm）

重新记录一个板子

1. 字符串下标从 $0$0开始（也可以很容易得改成从 $1$1开始）
2. $Z$Z数组的 $Z\left[0\right]$Z[0]不是良定义的，默认为 $0$0；如果有必要，可以在 $getZ\left(\right)$getZ()的最后进行 $Z\left[0\right]=n$Z[0]=n的修改
3. $S[j,j+z[j]-1]$S[j,j+z[j]−1]表示右端点最靠右的已匹配串
4. 求 $Z$Z数组的关键在于尽可能利用已求出的 $Z$Z数组值

char s[maxn];
int z[maxn];

void getZ() {
    int n=strlen(s);
    for(int i=1, j=0; i<n; ++i) {
        if(i<j+z[j]) z[i]=min(j+z[j]-i,z[i-j]);
        while(i+z[i]<n&&s[z[i]]==s[i+z[i]]) z[i]++;
        if(i+z[i]>j+z[j]) j=i;
    }
}