luoguP4770 [NOI2018]你的名字

题意

不妨先考虑\(l=1,r=|S|\)的情况：

这时我们要求的其实是\(S,T\)的本质不同的公共子串数量。

首先对\(S\)建一个后缀自动机，同时对于每个\(T\)，我们也建一个自动机。

根据后缀自动机的性质，后缀自动机的所有节点的代表的字符串的集合代表了\(T\)的全部子串，因此我们可以考虑\(T\)后缀自动机的上的每一个点代表的字符串中有多少是和\(S\)的公共子串。

于是考虑怎么求这个东西：

我们对于\(T\)的每一个前缀\(T[1...i]\)求出\(match_i\)表示这个前缀的后缀能跟\(S\)匹配的最长长度，这个东西可以在\(S\)的后缀自动机上匹配\(T\)来求出，见这题。

对于一个节点\(x\)，我们设它的字符串长度范围为\([minlen_x,maxlen_x]\)，\(endpos\)集合的第一个为\(firpos_x\)。

这时我们发现这个节点长度在\(match_{firpos_x}+1\)往上的字符串都不可能和\(S\)匹配，因此这个节点的贡献为\(\max(len_x-\max(len_{fa_x},match_{firpos_x}),0)\)。

现在考虑\([l,r]\)的限制，我们按照套路用线段树维护\(S\)的后缀自动机每个节点\(endpos\)集合，求\(match\)的时候只走合法的点即可。

求match时注意个细节，写在注释里了。

code:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e6+10;

int n,m,Q,tot,cnt_edge;

int head[maxn<<1],root[maxn<<1],match[maxn];

char s[maxn];

struct edge{int to,nxt;}e[maxn<<2];

struct Seg

{

	#define lc(p) (seg[p].lc)

	#define rc(p) (seg[p].rc)

	#define sum(p) (seg[p].sum)

	int lc,rc,sum;

}seg[maxn*50];

inline void add_edge(int u,int v)

{

	e[++cnt_edge].nxt=head[u];

	head[u]=cnt_edge;

	e[cnt_edge].to=v;

}

void insert(int &p,int l,int r,int pos)

{

	if(!p)p=++tot;

	sum(p)++;

	if(l==r)return;

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

	if(pos<=mid)insert(lc(p),l,mid,pos);

	else insert(rc(p),mid+1,r,pos);

}

int merge(int p,int q,int l,int r)

{

	if(!p||!q)return p+q;

	int x=++tot;sum(x)=sum(p)+sum(q);

	if(l==r)return x;

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

	lc(x)=merge(lc(p),lc(q),l,mid);

	rc(x)=merge(rc(p),rc(q),mid+1,r);

	return x;

}

int query(int p,int l,int r,int ql,int qr)

{

	if(!p)return 0;

	if(l>=ql&&r<=qr)return sum(p);

	int mid=(l+r)>>1,res=0;

	if(ql<=mid)res+=query(lc(p),l,mid,ql,qr);

	if(qr>mid)res+=query(rc(p),mid+1,r,ql,qr);

	return res;

}

void dfs(int x)

{

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

		dfs(e[i].to),root[x]=merge(root[x],root[e[i].to],1,n);

}

struct SAM

{

	int tot,last;

	int fa[maxn<<1],len[maxn<<1],firpos[maxn<<1];

	int ch[maxn<<1][30];

	inline void clear()

	{

		for(int i=1;i<=tot;i++)

		{

			fa[i]=len[i]=firpos[i]=0;

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

		}

		last=tot=1;

	}

	inline void add(int c,int id)

	{

		int now=++tot;len[now]=len[last]+1;firpos[now]=id;

		int p=last;last=now;

		while(p&&!ch[p][c])ch[p][c]=now,p=fa[p];

		if(!p){fa[now]=1;return;}

		int q=ch[p][c];

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

		else

		{

			int nowq=++tot;len[nowq]=len[p]+1;firpos[nowq]=firpos[q];

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

			fa[nowq]=fa[q];fa[q]=fa[now]=nowq;

			while(p&&ch[p][c]==q)ch[p][c]=nowq,p=fa[p];

		}

	}

}sam1,sam2;

inline int read()

{

	char c=getchar();int res=0,f=1;

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

	while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();

	return res*f;

}

inline void getmatch(char* s,int l,int r)

{

	int len=strlen(s+1),now=1,nowl=0;

	for(int i=1;i<=len;i++)

	{

		while(2333)

		{

			if(sam1.ch[now][s[i]-'a']&&query(root[sam1.ch[now][s[i]-'a']],1,n,l+nowl,r))//注意是l+nowl，这是endpos的集合。

			{

				now=sam1.ch[now][s[i]-'a'],nowl++;

				break;

			}

			if(!nowl)break;

			nowl--;//注意不要直接跳fa[now],因为区间缩小可能产生答案。

			if(nowl==sam1.len[sam1.fa[now]])now=sam1.fa[now];

		}

		match[i]=nowl;

	}

}

int main()

{

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

	sam1.clear();

	for(int i=1;i<=n;i++)sam1.add(s[i]-'a',i),insert(root[sam1.last],1,n,i);

	for(int i=2;i<=sam1.tot;i++)add_edge(sam1.fa[i],i);

	dfs(1);

	Q=read();

	while(Q--)

	{

		ll ans=0;

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

		int l=read(),r=read();

		sam2.clear();

		for(int i=1;i<=m;i++)sam2.add(s[i]-'a',i);

		getmatch(s,l,r);

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

			ans+=max(0,sam2.len[i]-max(match[sam2.firpos[i]],sam2.len[sam2.fa[i]]));

		printf("%lld\n",ans);

	}

	return 0;

}

巴特西

luoguP4770 [NOI2018]你的名字

题意

最新文章

热门文章