给定长 的字符串 ,对于每个 ,求出 表示 。
时间复杂度 。
类似 manacher,若存在 满足 且 ,则 至少为 :

那么记录 最大的 ,每次暴力拓展 都会令 增加 ,所以时间复杂度均摊 。
注意 要单独计算。
代码如下:
z[1]=n;
for(int i=2,rb=2;i<=n;i++)
{
if(rb+z[rb]-1>=i) z[i]=min(z[i-rb+1],rb+z[rb]-i);
while(z[i]<n-i+1&&a[z[i]+1]==a[i+z[i]]) z[i]++;
if(i+z[i]>rb+z[rb]) rb=i;
}
练习题目: