```cpp
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxN 1000005
string str1, str2;
int len1, len2;
int next[maxN];
void getnext() {
next[0]=-1;
for (int i=1;i < len2;i++) {
int j=next[i-1];
while (str2[i] != str2[j+1] && j >= 0) {
j=next[j];
}
if (str2[i] == str2[j+1]) {
next[i]=j+1;
} else {
next[i]=-1;
}
}
}
void KMP() {
int k1=0, k2=0;
bool pd=false;
while (k1 < len1) {
if (str1[k1] == str2[k2]) {
k1++;
k2++;
} else
if (k2 == 0) {
k1++;
} else {
k2=next[k2-1]+1;
}
if (k2 == len2) {
pd=true;
cout << k1-k2+1 << endl;
k2=next[k2-1]+1;
}
}
if (!pd) cout << 0 << endl;
}
int main() {
ios::sync_with_stdio(false);
cin >> str1 >> str2;
len1=str1.length();
len2=str2.length();
getnext();
KMP();
for (int i=0;i < len2;i++) {
cout << next[i]+1 << " ";
}
return 0;
}
```
by alw008 @ 2017-11-01 19:22:51
没有问题吧。。。
你拿数据去洛谷IDE测试一下呗
我的代码在洛谷上直接炸掉,疯狂输出有序数字
(表示当场笑哭)
by Robert @ 2017-11-01 19:45:03
几个月前一模一样的题解在洛谷上AC了,今天再交就70分了,是不是加了新的数据点,反正我最后三个点全TLE了
by yoyo @ 2017-11-02 19:32:56
tle了
by 罪将于禁 @ 2017-11-03 10:41:48