Z——BOX算法:
对于一个字符串$s$,设它的长度为$len$
$z[i]$所表示的是$s[i…len-1]$与$s[0…len-1]$的最长公共前缀
代码:
void getz(int n,char *str){
int l = 0,r = 0;
z[1] = n;
for(int i = 2;i <= n;i ++){
if(i > r){
while(str[i + z[i]] == str[1 + z[i]])
z[i] ++;
l = i,r = i + z[i] - 1;
}
else if(z[i - l + 1] < r - i + 1)
z[i] = z[i - l + 1];
else{
z[i] = r - i;
while(str[i + z[i]] == str[1 + z[i]])
z[i] ++;
l = i,r = i + z[i] - 1;
}
}
}