CF666E Forensic Examination（后缀自动机+线段树合并）

给你一个串S以及一个字符串数组T[1..m]，q次询问，每次问S的子串S[pl..pr]在T[l..r]中的哪个串里的出现次数最多，并输出出现次数。

如有多解输出最靠前的那一个。

我们首先对m个字符串数组建出后缀自动机，然后我们可以通过跳trans边找到S前i个字符代表的前缀的最长后缀。我们要找的是S[pl..pr]并不是以pr结束最长的后缀，但我们可以确定S[pl..pr]一定是当前点的祖先所以当我们跳到pr代表的点时我们倍增往上跳知道找到一个点的长度刚好大于等于pr-pl+1，这个点就是询问区间代表的点。

那么我们怎么求答案呢？上线段树合并就行（线段树以[1,m]为值域），这就要求我们对询问离线。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

const int N=501000;

int n,m,L;

char S[N],s[N];

int cnt,head[N];

struct edge{

	int to,nxt;

}e[N];

void add(int u,int v){

	cnt++;

	e[cnt].nxt=head[u];

	e[cnt].to=v;

	head[u]=cnt;

}

struct ques{

	int l,a,b,id;

	ques(int ll=0,int aa=0,int bb=0,int idx=0){

		l=ll;a=aa;b=bb;id=idx;

	}

};

struct data{

	int mx,id;

	data(int mxx=0,int idx=0){

		mx=mxx;id=idx;

	}

}ans[N];

struct qu{

	int a,b,id;

	qu(int idx=0,int aa=0,int bb=0){

		a=aa;b=bb;id=idx;

	}

};

vector<qu> que[N];

data max(data a,data b){

	if(a.mx==b.mx){

		if(a.id<b.id)return a;

		return b;

	}

	if(a.mx>b.mx)return a;

	return b;

}

vector<ques> vec[N];

struct sam{

	int tot,u,trans[N][27],fa[N][23],len[N];

	int root[N],ch[N*50][2],cnt,mx[N*50],id[N*50];

	void init(){tot=u=1;}

	void rebuild(){u=1;}

	void ins(int k,int c){

		if(trans[u][c]){

			int v=trans[u][c];

			if(len[v]==len[u]+1)u=v,add(1,m,k,root[v]);

			else{

				int x=++tot;add(1,m,k,root[x]);len[x]=len[u]+1;

				memcpy(trans[x],trans[v],sizeof(trans[v]));

				fa[x][0]=fa[v][0];fa[v][0]=x;

				for(;u&&trans[u][c]==v;u=fa[u][0])trans[u][c]=x;

				u=x;

			}

		}

		else{

			int x=++tot;add(1,m,k,root[x]);len[x]=len[u]+1;

			for(;u&&trans[u][c]==0;u=fa[u][0])trans[u][c]=x;

			if(u==0)fa[x][0]=1;

			else{

				int v=trans[u][c];

				if(len[v]==len[u]+1)fa[x][0]=v;

				else{

					int w=++tot;

					len[w]=len[u]+1;

					fa[w][0]=fa[v][0];

					memcpy(trans[w],trans[v],sizeof(trans[w]));

					fa[x][0]=fa[v][0]=w;

					for(;u&&trans[u][c]==v;u=fa[u][0])trans[u][c]=w;

				}

			}

			u=x;

		}

	}

	void update(int now){

		if(mx[ch[now][0]]>=mx[ch[now][1]])mx[now]=mx[ch[now][0]],id[now]=id[ch[now][0]];

		else mx[now]=mx[ch[now][1]],id[now]=id[ch[now][1]];

	}

	void add(int l,int r,int x,int &now){

		if(now==0)now=++cnt;

		if(l==r){mx[now]++;id[now]=l;return;}

		int mid=(l+r)>>1;

		if(x>mid)add(mid+1,r,x,ch[now][1]);

		else add(l,mid,x,ch[now][0]);

		update(now);

	}

	data check(int l,int r,int L,int R,int now){

		if(l==L&&r==R)return (data(mx[now],id[now]));

		int mid=(l+r)>>1;

		if(L>mid)return check(mid+1,r,L,R,ch[now][1]);

		else if(R<=mid)return check(l,mid,L,R,ch[now][0]);

		else return max(check(l,mid,L,mid,ch[now][0]),check(mid+1,r,mid+1,R,ch[now][1]));

	}

	void merge(int l,int r,int &x,int y){

		if(!x||!y){x=x|y;return;}

		if(l==r){mx[x]+=mx[y];return;}

		int mid=(l+r)>>1;

		merge(l,mid,ch[x][0],ch[y][0]);

		merge(mid+1,r,ch[x][1],ch[y][1]);

		update(x);

	}

	void dfs(int u){

		for(int i=head[u];i;i=e[i].nxt){

			int v=e[i].to;

			dfs(v);

			merge(1,m,root[u],root[v]);

		}

		for(int i=0;i<que[u].size();i++){

			data a=check(1,m,que[u][i].a,que[u][i].b,root[u]);

			if(a.mx==0)continue;

			ans[que[u][i].id]=a;

		}

	}

	void work(){

		int now=1;

		int lon=0;

		for(int i=1;i<=L;i++){

			while(trans[now][S[i]-'a'+1]==0&&now)now=fa[now][0],lon=len[now];

			if(now==0){

				for(int j=0;j<vec[i].size();j++)ans[vec[i][j].id].id=vec[i][j].a;

				now=1;lon=0;continue;

			}

			now=trans[now][S[i]-'a'+1];lon++;

			for(int j=0;j<vec[i].size();j++){

				ans[vec[i][j].id].id=vec[i][j].a;

				if(lon<i-vec[i][j].l+1)continue;

				int x=now;

				for(int k=20;k>=0;k--)

                	if(len[fa[x][k]]>=i-vec[i][j].l+1)x=fa[x][k];

                qu a=qu(vec[i][j].id,vec[i][j].a,vec[i][j].b);

                que[x].push_back(a);

			}

		}

	}

}sam;

int read(){

	int sum=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}

	return sum*f;

}

int main(){

	scanf("%s",S+1);

	scanf("%d",&m);

	sam.init();

	for(int i=1;i<=m;i++){

		scanf("%s",s+1);

		int len=strlen(s+1);

		for(int j=1;j<=len;j++)sam.ins(i,s[j]-'a'+1);

		sam.rebuild();

	}

	for(int i=2;i<=sam.tot;i++)add(sam.fa[i][0],i);

	for(int j=1;j<=20;j++)

		for(int i=2;i<=sam.tot;i++)

			sam.fa[i][j]=sam.fa[sam.fa[i][j-1]][j-1];

	scanf("%d",&n);

	for(int i=1;i<=n;i++){

		int c=read(),d=read(),a=read(),b=read();

		vec[b].push_back(ques(a,c,d,i));

	}

	L=strlen(S+1);

	sam.work();

	sam.dfs(1);

	for(int i=1;i<=n;i++)printf("%d %d\n",ans[i].id,ans[i].mx);

	return 0;

}

巴特西

CF666E Forensic Examination（后缀自动机+线段树合并）

最新文章

热门文章