@[Lucifer1115](/space/show?uid=59357) 那你的nxt数组锅也很大啊qwq
by Styx @ 2018-08-05 19:51:42
@[Lucifer1115](/space/show?uid=59357) 大概要有两点问题,你的nxt数组只开了10w,应该改开到100w+10,你的s1,s2应该也开到100w+10左右,因为数组的最后一位是不能存东西的
by Styx @ 2018-08-05 19:53:52
@[Styx](/space/show?uid=48740) 我突然醒悟,然后改了去试。然而 又玄学 WA了还是 too many or too few line。是不是答案行不够,还是nxt有问题。
by Lucifer1115 @ 2018-08-05 22:43:56
@[Lucifer1115](/space/show?uid=59357) 啊?我用你第一个程序改完三个数据范围A掉了啊?
代码如下:
```cpp
#include<bits/stdc++.h>
using namespace std;
char s1[1100000],s2[1100000];
int nxt[1100000],l1,l2,ans;
void prework()
{
nxt[0]=nxt[1]=0;
for(int i=2,j=0;i<=l2;i++)
{
while(j && s2[i]!=s2[j+1])j=nxt[j];
if(s2[i]==s2[j+1])j++;
nxt[i]=j;
}
}
void kmp()
{
for(int i=1,j=0;i<=l1;i++)
{
while(j && s1[i]!=s2[j+1])j=nxt[j];
if(s1[i]==s2[j+1])j++;
if(j==l2)
{
printf("%d\n",i-l2+1);
j=nxt[j];
}
}
}
int main()
{
scanf("%s%s",s1+1,s2+1);
l1=strlen(s1+1);
l2=strlen(s2+1);
prework();
kmp();
for(int i=1;i<=l2;i++)
{
printf("%d ",nxt[i]);
}
return 0;
}
```
by Styx @ 2018-08-06 07:44:28
@[Styx](/space/show?uid=48740) 真的啊!! 可能是我人品问题。我再试试。
by Lucifer1115 @ 2018-08-06 19:10:24
@[Styx](/space/show?uid=48740) 真的是!! 谢谢神犇大佬。
by Lucifer1115 @ 2018-08-06 19:14:19