RT,这篇题解貌似写的有问题。
具体问题大概出在求 kmp 数组的时候。
for(int i=1;i<=n;i++){
next[i][i]=0;
for(int j=i+1,v=0;j<=n;j++){
while(v && str[j] != str[i+v])v=next[i][v];//这里应该是next[i+v-1]
if(str[j]==str[i+v])v++;
next[i][j]=v;
}
}
hack数据:
abbabbb
题解输出 3,正确答案应为 2,方式为:
- 将两个 abb 缩起来,形成 abbb。
- 将后面那一堆 b 缩起来,形成 ab。