重新记录一个板子

  1. 字符串下标从 0 0 0开始（也可以很容易得改成从 1 1 1开始）
  2. Z Z Z数组的 Z [ 0 ] Z[0] Z[0]不是良定义的，默认为 0 0 0；如果有必要，可以在 g e t Z ( ) getZ() getZ()的最后进行 Z [ 0 ] = n Z[0]=n Z[0]=n的修改
  3. S [ j , j + z [ j ] − 1 ] S[j,j+z[j]-1] S[j,j+z[j]−1]表示右端点最靠右的已匹配串
  4. 求 Z Z 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;
    }
}