被 hack 的情况,题解里说的很清楚了,原因就是 next 数组没有按照同样的逻辑去求,导致失配后 next 数组匹配不上。
然后就是wa三个点的情况,感觉很玄学,我本来求next的代码是这样的
string a[N],b[N];
int s[N],t[N];
int kmp_next[N];
bool check(int i,int j){
return (i-s[i]==j-t[j]||s[i]<i-j&&t[j]==-inf);
}
bool check1(int i,int j){
return (i-t[i]==j-t[j]||t[i]<i-j&&t[j]==-inf);
}
void getNext(int m){
int j = 0;
kmp_next[0] = 0;
for(int i=1; i<m; ++i){
while(j>0 && check1(i,j)) j=kmp_next[j-1];
if(check1(i,j)) ++j;
kmp_next[i] = j;
}
}
改完之后就ac了
void getNext(int m){
int j = 0;
kmp_next[0] = 0;
for(int i=1; i<m; ++i){
if(check1(i,j)) ++j;
else while(j>0 && check1(i,j)) j=kmp_next[j-1];
kmp_next[i] = j;
}
}
有无佬解释,玄关