好像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