来自洛谷P3375 【模板】KMP 题解,提交失败
代码:
#include "iostream"
using std::cin;
using std::cout;
using std::endl;
using std::strlen;
char a[1000005], b[1000005];
int next[1000005];
int lena, lenb;
int main() {
cin >> a + 1 >> b + 1;
lena = strlen(a + 1);
lenb = strlen(b + 1);
next[1] = 0;
int j = 0;
for (int i = 2; i <= lenb; i++) {
while (j > 0 && b[i] != b[j + 1])j = next[j];
if (b[i] == b[j + 1])j++;
next[i] = j;
}
j = 0;
for (int i = 1; i <= lena; i++) {
while (j > 0 && a[i] != b[j + 1])j = next[j];
if (a[i] == b[j + 1])j++;
if (j == lenb)cout << i - j + 1 << endl;
}
for (int i = 1; i <= lenb; i++) {
cout << next[i] << ' ';
}
}