正题

题目链接:https://www.luogu.com.cn/problem/P4770

题目大意

给出一个长度为\(n\)的字符串\(S\)。\(q\)次询问给出一个串\(T\)和一个区间\([L,R]\)，求\(T\)有多少个本质不同的子串不是\(S_{L\sim R}\)的子串。

\(1\leq n\leq 5\times 10^5,1\leq Q\le 10^5,\sum|T|\leq 10^6\)

解题思路

因为给了很多\(L=1,R=n\)的部分分所以应该是提示我们先从这个方面考虑。

这个部分比较简单，考虑改为求有多少个本质不同的子串在\(S_{L\sim R}\)中出现过，因为是本质不同的子串，我们可以先建一个\(S\)的\(SAM\)和一个\(T\)的\(SAM\)。

然后把\(T\)串拿到\(S\)的\(SAM\)上面跑，然后每次跑出来的一个匹配长度记为\(len\)。对于\(T\)的\(SAM\)上的每一个节点我们记录一个\(pos\)表示这个节点属于的长度位置，然后跑到这个位置的\(len\)就是能够匹配的长度了，记为\(ans\)。然后答案就是\(max\{len_i-max\{ans_{pos_i},len_{fa_i}\},0\}\)（防匹配长度超出\([len_{fa_i},len_i]\)的范围）

这样一次的时间复杂度就是\(O(|T|)\)的了。

然后考虑带区间的怎么做，我们需要保证我们在\(S\)的\(SAM\)上面跳的时候需要保证这些节点都是属于\(S_{L\sim R}\)的自动机上的，而且要保证我们提取出来的\(len\)也是在那个上面的。

其实如果这个节点的\(endpos\)类里面有\(L\sim R\)的信息就好了，这个用线段树合并维护一下\(endpos\)类的信息就可以了。

时间复杂度\(O((n+\sum |T|)\log n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=1e6+10;

int n,q,ql,qr,p[N],c[N],rt[N],ans[N],pos[N];

char s[N];

struct SegTree{

	int cnt,w[N<<5],ls[N<<5],rs[N<<5];

	int Change(int x,int L,int R,int pos){

		int p=++cnt;w[p]=max(w[x],pos);

		if(L==R)return p;int mid=(L+R)>>1;

		if(pos<=mid)ls[p]=Change(ls[x],L,mid,pos),rs[p]=rs[x];

		else rs[p]=Change(rs[x],mid+1,R,pos),ls[p]=ls[x];

		return p;

	}

	int Ask(int x,int L,int R,int l,int r){

		if(!x)return 0;

		if(L==l&&R==r)return w[x];

		int mid=(L+R)>>1;

		if(r<=mid)return Ask(ls[x],L,mid,l,r);

		if(l>mid)return Ask(rs[x],mid+1,R,l,r);

		return max(Ask(ls[x],L,mid,l,mid),Ask(rs[x],mid+1,R,mid+1,r));

	}

	int Merge(int x,int y){

		if(!x||!y)return x+y;

		int p=++cnt;w[p]=max(w[x],w[y]);

		ls[p]=Merge(ls[x],ls[y]);

		rs[p]=Merge(rs[x],rs[y]);

		return p;

	}

}R;

struct SAM{

	int cnt,last,ch[N][26],len[N],fa[N];

	void init(){

		memset(ch[1],0,sizeof(ch[1]));

		last=cnt=1;

	}

	int Insert(int c){

		int p=last,np=last=++cnt;

		len[np]=len[p]+1;

		memset(ch[np],0,sizeof(ch[np]));

		for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;

		if(!p)fa[np]=1;

		else{

			int q=ch[p][c];

			if(len[p]+1==len[q])fa[np]=q;

			else{

				int nq=++cnt;len[nq]=len[p]+1;

				memcpy(ch[nq],ch[q],sizeof(ch[nq]));

				fa[nq]=fa[q];fa[q]=fa[np]=nq;pos[nq]=pos[q];

				for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nq;

			}

		}

		last=np;return np;

	}

	void Build(){

		for(int i=1;i<=cnt;i++)c[len[i]]++;

		for(int i=1;i<=n;i++)c[i]+=c[i-1];

		for(int i=1;i<=cnt;i++)p[c[len[i]]--]=i;

		for(int i=cnt;i>=1;i--){

			int x=p[i];

			rt[fa[x]]=R.Merge(rt[fa[x]],rt[x]);

		}

		return;

	}

	void next(int &x,int &l,int c){

		while(x){

			if(ch[x][c]){

				int maxl=R.Ask(rt[ch[x][c]],1,n,1,qr)-ql+1;

				if(len[fa[x]]<maxl){l=min(l+1,maxl);x=ch[x][c];return;}

			}

			x=fa[x];l=len[x];

		}

		l=0;x=1;return;

	}

	ll calc(){

		ll prt=0;

		for(int i=2;i<=cnt;i++)

			prt+=max(len[i]-max(ans[pos[i]],len[fa[i]]),0);

		return prt;

	}

}S,T;

void work(char *s){

	int m=strlen(s+1);T.init();

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

		int x=T.Insert(s[i]-'a');

		pos[x]=i;

	}

	int x=1,l=0;

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

		int c=s[i]-'a';

		S.next(x,l,c);

		ans[i]=l;

	}

	printf("%lld\n",T.calc());

}

signed main()

{

	scanf("%s",s+1);n=strlen(s+1);

	S.init();

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

		int x=S.Insert(s[i]-'a');

		rt[x]=R.Change(rt[x],1,n,i);

	}

	S.Build();

	scanf("%d",&q);

	while(q--){

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

		scanf("%d%d",&ql,&qr);

		work(s);

	}

	return 0;

}

巴特西

P4770-[NOI2018]你的名字【SAM,线段树合并】

正题

题目大意

解题思路

code

最新文章

热门文章