**对于你的测试点:**
输出:
19
22
26
0 0
你的输出:
4
8
12
15
19
22
26
30
34
39
43
49
54
58
62
67
71
75
80
83
0 0
**初步怀疑没有匹配 $ s2 $ 串第 $ 1 $ 位.**
**验证:**
abacabadabaeaba
daba
输出:
8
0 0 0 0
你的输出:
4
8
12
0 0 0 0
**基本验证猜测.**
**错误排查:**
首先检查 $ next $ 的计算,经验证没有问题,基本可以确定问题出在用 $ s2 $ 匹配 $ s1 $ 的环节,即 $ search() $.
在
```cpp
1 inline void search(){
2 int j=0;
3 for(int i=1;s1[i];i++)
4 {
5 while(j&&s2[j+1]!=s1[i])
6 j=next[j];
7 if(s2[j+1]==s1[i])
8 j++;
9 if(j+1==s2.size())
10 cout<<i-s2.size()+2<<endl;
11 }
12 }
```
这一段中,可以调试发现,当第 6 行 $j$ 被赋值为 $ next[j]=0 $ 之后,下一次循环时,第 5 行判断 $ s2[j+1] $ 是否等于 $ s1[i] $ 时,判断的是 $ s2[1] $ 是否等于 $ s1[1] $ ,也就是说跳过了比较 $ s2[0] $ 和 $ s1[0] $ .
最方便的修改方法就是把 $ i $ 和 $ j $ 的值全部减去 $ 1 $.
修改该函数如下:
```cpp
1 inline void search(){
2 int j=0;
3 for(int i=1;s1[i-1];i++)
4 {
5 while(j&&s2[j]!=s1[i-1])
6 j=next[j];
7 if(s2[j]==s1[i-1])
8 j++;
9 if(j==s2.size())
10 cout<<i-s2.size()+1<<endl;
11 }
12 }
```
最后再做一些小的细节修改,移除没有使用的 $ ans $ 数组,并为 $ int $ 和 $ unsigned $ $ int $ 之间的比较添加了强制类型转换。
完整代码如下:
[AC评测记录](https://www.luogu.org/recordnew/show/12300088)
```cpp
#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int next[1000001];
inline void get_next()
{
int j=0;
for(int i=1;s2[i];i++)
{
while(j&&s2[j]!=s2[i]) j=next[j];
if(s2[j]==s2[i]) j++;
next[i+1]=j;
}
}
inline void search()
{
int j=0;
for(int i=1;s1[i-1];i++)
{
while(j&&s2[j]!=s1[i-1])
j=next[j];
if(s2[j]==s1[i-1])
j++;
if(j==(int)(s2.size()))
cout<<i-s2.size()+1<<endl;
}
}
int main(){
cin>>s1>>s2;
get_next();
search();
for(int i=1;i<=(int)(s2.size());i++)
cout<<next[i]<<' ';
}
```
by _frostLotus @ 2018-10-23 02:28:35
@[非正常智障](/space/show?uid=92496)
by _frostLotus @ 2018-10-23 02:29:14
另外希望出题人加强数据,以便大家平时刷题时能够尽快发现自己程序的 BUG 并加以修改,避免因此造成的误导使得大家在考场上失分。
@[HansBug](/space/show?uid=1492)
by _frostLotus @ 2018-10-23 02:31:57
@[_Realizer](/space/show?uid=48388) 哇,大佬太强了,谢谢大佬
by 文武武智障 @ 2018-10-23 07:23:54