社区讨论
闲得蛋疼回顾KMP模板居然WA了?
P3375【模板】KMP参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @m3zzzrnv
- 此快照首次捕获于
- 2024/11/27 22:45 去年
- 此快照最后确认于
- 2024/11/28 08:07 去年
CPP
#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int Next[1000010],len1,len2;
void getNext(string p,int lenp) {
Next[0] = Next[1] = 0;
for (int i = 1;i < lenp;i ++) {
int j = Next[i];
while (j && p[i] != p[j])
j = Next[j];
if (p[i] == p[j]) Next[i + 1] = j + 1;
else Next[i + 1] = 0;
}
return;
}
void kmp(string s,string p,int lens,int lenp) {
int j = 0;
getNext(p,lenp);
for (int i = 0;i < s.size();i ++) {
while (j && s[i] != p[j])
j = Next[j];
if (s[i] == p[j]) ++ j;
if (j == lenp) {//return i - lenp + 1;
printf("%d\n",i - lenp + 1 + 1);
j = Next[j];
}
}
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> s1 >> s2;
len1 = s1.size();
len2 = s2.size();
kmp(s1,s2,len1,len2);
for (int i = 0;i < s2.size();i ++)
cout << Next[i + 1] << " ";
cout << "\n";
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...