悬关/警示后人(如果你被hack/改完hack连wa三个点)
查看原帖
悬关/警示后人(如果你被hack/改完hack连wa三个点)
1085807
swww77楼主2024/10/21 19:18

hackhack 的情况,题解里说的很清楚了,原因就是 nextnext 数组没有按照同样的逻辑去求,导致失配后 nextnext 数组匹配不上。

然后就是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;
	}
}   

有无佬解释,玄关

2024/10/21 19:18
加载中...