警示后人：如果你把两个串合起来算且 TLE #7,12

由于把两个字符串拼起来算，因此两个数组不能越界，例如计算 b 串

i

位置的

z_i

时，应满足

i+z_i \le size(b)

。

但是为了避免这种情况，你不能用这种方法求解 z 函数：

CPP

for(int i=1,l=0,r=0;i<len;i++){
  if(i<=r&&z[i-l]<r-i+1)z[i]=z[i-l];
  else{
    z[i]=max(0,r-i+1); 
    while(i+z[i]<len&&b[z[i]]==b[i+z[i]])++z[i];
  }
  if(i<len2)z[i]=min(z[i],len2-i);// 这里
  if(r<i+z[i]-1)l=i,r=i+z[i]-1;
}

注意到越界本身对计算前缀这种东西没有影响（即使从

b_i

开始的 lcp 跑到了

a

的范围里去，它依然是和

b

的 lcp，可以参与对各

a_i

的贡献），因此我们只需在统计答案时取个 min 即可，不需要 for 循环里的那一句话。

警示后人：如果你把两个串合起来算且 TLE #7,12

讨论操作

回复

相关推荐

警示后人：如果你把两个串合起来算且 TLE #7,12