【求助+半题解】BZOJ1461字符串的匹配

发布时间 2023-07-21 09:10:39作者: Sonnety

先说思路:
因为我们是比对较短的\(B\)与较长的\(A\)的子串,所以我们求不变的\(B\)\(next\)

对于这道题我们可以使用树状数组查询前缀和维护数的排名。

对于相同的数我们查询的排名是有误的,因此不仅要比对小于等于该数的前缀和,也要比对小于该数的前缀和。

如:对于\(A=2\) \(2\),\(B=1\) \(2\),来说,\(A\)的第二个\(2\)排名应为\(1\),但是前缀和是\(2\)

对于代码有一求助问题。

点击查看代码
#include<bits/stdc++.h>
using namespace std;

const int maxn=5e6+50;

int n,k,s,next_[maxn];
int A[maxn],B[maxn],c[maxn];
int ranq[maxn],ress[maxn];
int ans,anss[maxn]; 

int lowbit(int x){
	return x&(-x);
}

void update(int x,int y){
	while(x<=s){
		c[x]+=y;
		x+=lowbit(x);
	}
}

int query(int x){
	int ans2=0;
	while(x){
		ans2+=c[x];
		x-=lowbit(x);
	}
	return ans2;
}

inline void input(){
	scanf("%d %d %d",&n,&k,&s);
	for(int i=1;i<=n;++i){
		scanf("%d",&A[i]);
	}
	for(int i=1;i<=k;++i){
		scanf("%d",&B[i]);
		update(B[i],1);
		ranq[i]=query(B[i]);
		ress[i]=query(B[i]-1);
		//cout<<"%%%"<<i<<' '<<ranq[i]<<' '<<ress[i]<<endl;
	}
}

inline void Next(){
	for(int i=2,j=0;i<=k;++i){
		while(j && (query(B[i])!=ranq[j+1] || query(B[i]-1)!=ress[j+1])){
			j=next_[j];
		}
		++j;
		next_[i]=j;
	}
}

inline void match(){
	for(int i=1,j=0;i<=n;++i){
		update(A[i],1);
		while(j &&(query(A[i])!=ranq[j+1] || query(A[i]-1)!=ress[j+1])){
			//cout<<i<<' '<<j+1<<' '<<A[i]<<' '<<query(A[i])<<' '<<ranq[j+1]<<' '<<query(A[i]-1)<<' '<<ress[j+1]<<endl;
			for(int q=i-j;q<i-next_[j];++q){
				update(A[q],-1);
				//比对相同区间把前面的删去
			}
			//cout<<"$$$"<<j<<' '<<next_[j]<<endl;
			j=next_[j];
		}
		//cout<<"###"<<i<<' '<<j<<endl;
		j++;
		if(j==k)	anss[++ans]=i-j+1;
	}
}

int main(){
	input();
	Next();
	memset(c,0,sizeof(c));
	match();
	printf("%d\n",ans);
	for(int i=1;i<=ans;++i){
		printf("%d\n",anss[i]);
	} 
	return 0;
}


我们可以看到\(next\)我写的是:

inline void Next(){
	for(int i=2,j=0;i<=k;++i){
		while(j && (query(B[i])!=ranq[j+1] || query(B[i]-1)!=ress[j+1])){
			j=next_[j];
		}
		++j;
		next_[i]=j;
	}
}

前面也没有清空树状数组。

但是网上的很多题解都写的是:

void get_next(){
    memset(BIT, 0, sizeof(BIT));
    next[1] = 0;
    int i = 2, j = 0, k;
    for (; i <= m; ++i){
        add(b[i], 1);
        while (j && (query(b[i] - 1) != les[j + 1] || query(b[i]) != equ[j + 1])){
            for (k = i - j; k < i - next[j]; ++k)
                add(b[k], -1);
            j = next[j];
        }
        next[i] = ++j;
    }
}

题解来源

我与mp讨论后认为,不清空才是正确的,因为求\(next\)的过程中我们没有将第一个数字放入树状数组,对前缀和一定是有影响的,但是事实上,两种写法都AC了这道题目。

求解答。