在洛谷做一道KMP很基础的题
大致就是查找所有子串出现的位置
再打印next数组
一个测试点过不了它属于很长的字符串
```c++
#include<iostream>
#include<string.h>
#include<string>
using namespace std;
const int L = 1e6+10;
void KMP(char *S, char *T, int next[]) {
int i = 0, j = 0, flag = 0;
int lenS = strlen(S);
int lenT = strlen(T);
while (i < lenS) {
if (S[i] == T[j] || j == -1) {
i++;
j++;
}
else {
j = next[j];
}
if (j == lenT) {
flag = 1;
cout << i - j + 1 << endl;
j = next[j];
}
}
if (flag == 0) {
cout << -1;
}
return;
}
void getNext(char *T, int* next) {
int i = 0, j = -1;
next[0] = -1;
int lenT =strlen(T);
while (i < lenT) {
if (j == -1 || T[i] == T[j]) {
i++;
j++;
next[i] = j;
}
else {
j = next[j];
}
}
return;
}
int main() {
char s1[L], s2[L];
scanf("%s",s1);
scanf("%s",s2);
int next[L]={0};
getNext(s2, next);
KMP(s1, s2, next);
int i=0,len=strlen(s2);
for(i=1;i<len;i++){
cout<<next[i]<<" ";
}
cout<<next[i]<<endl;
return 0;
}
代码如上，
具体情况就是我复制粘贴那个测试点，就不执行。
我猜是scanf()的问题。
其实cin
scanf
我真的搞不懂
