社区讨论

闲得蛋疼回顾KMP模板居然WA了?

灌水区参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@m40hat0f
此快照首次捕获于
2024/11/28 06:49
去年
此快照最后确认于
2024/11/28 08:06
去年
查看原帖
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;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...