这题好像s-t匹配的时候不能用kmp
查看原帖
这题好像s-t匹配的时候不能用kmp
315205
Kniqht楼主2023/11/11 06:36

好像kmp无法处理问号的情况,我在kmp的时候将?看作能与任何字符匹配,就错了。

这是为什么呢?

//	for(int i=1,j=0;i<=n;i++){
//		while(j&&(s[i]!='?'&&s[i]!=t[j+1])) j=ne[j];
//		if(s[i]==t[j+1]||s[i]=='?') j++;
//		if(j==m){
//			st[i]=1;
//			j=ne[j];
//		}
//	}注释掉的kmp匹配代码

正确的暴力匹配代码:

bool check(int p){
	for(int j=1;j<=m;j++)
		if(s[p-j+1]!=t[m-j+1]&&s[p-j+1]!='?') return 0;
	return 1;
}

and 完整代码https://codeforces.com/contest/808/submission/232304708

2023/11/11 06:36
加载中...