30WA求助,第一次做KMP可能问题比较多
查看原帖
30WA求助,第一次做KMP可能问题比较多
372602
Lil_Y楼主2024/7/16 16:43

代码如下,比对了数据5貌似连文本串长度都错了???数对得上但是后面部分都漏了。还有为什么编译只有C++98能过,救命我啥也不懂

#include<bits/stdc++.h>

using namespace std;
string s,ss;
int next[1000100];
int main() {

	cin>>s;
	cin>>ss;
	if(ss.length()>1) {

		int j=0;
		next[0]=0;
		for(register int i=1; i<ss.length(); i++) {
			while(j>0&&ss[i]!=ss[j]) {
				j=next[j-1];
			}
			if(ss[i]==ss[j]) {
				j++;
			}
			next[i]=j;
		}//kmp预处理 
		j=0;
		for(register int i=0; i<s.length(); i++) {
			if(s[i]==ss[j]) {
				j++;
				if(j==ss.length()) {// 找到完整模式串 
					printf("%d\n",i+2-ss.length());
					j=next[j]+1;
				}
			} else {
				j=next[j-1]+1;
			}

		}
		for(register int i=0; i<ss.length(); i++)
			printf("%d ",next[i]);
		return 0;
	}
	
	for(register int i=0; i<s.length(); i++) {
		if(s[i]==ss[0])
			printf("%d\n",i+1);
	}
	cout<<0<<endl;
	return 0;
}
2024/7/16 16:43
加载中...