Luogu4770 NOI2018你的名字（后缀自动机+线段树合并）

佚名 7年前 (2019-05-06) 随笔 1228人围观抢沙发百度已收录

　　先考虑l=1,r=n，并且不要求本质不同的情况。对原串建SAM，将询问串在上面跑，得到每个前缀的最长匹配后缀即可得到答案。

　　然后考虑本质不同。对询问串也建SAM，统计每个节点的贡献，得到该点right集合中任意一个的匹配长度即可。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

　　然后考虑原问题。我们需要求的仍然只是每个前缀的最长匹配后缀。通过线段树合并得到原串SAM每个点的right集合，同样将询问串在上面跑，跑的时候根据所达点right集合在给定区间中的最大值得到该点极限匹配长度，判断是否能在该点匹配（即极限匹配长度是否不小于该点所表示的最短长度），若不能则跳fail。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
char s[N];
int Q,match[N],tmp[N],root[N],cnt;
struct data{int l,r,x;
}tree[N*40];
void ins(int &k,int l,int r,int x)
{
	tree[++cnt]=tree[k],k=cnt;tree[k].x=max(tree[k].x,x);
	if (l==r) return;
	int mid=l+r>>1;
	if (x<=mid) ins(tree[k].l,l,mid,x);
	else ins(tree[k].r,mid+1,r,x);
}
int merge(int x,int y,int l,int r)
{
	if (!x||!y) return x|y;
	int k=++cnt;
	tree[k].x=max(tree[x].x,tree[y].x);
	if (l<r)
	{
		int mid=l+r>>1;
		tree[k].l=merge(tree[x].l,tree[y].l,l,mid);
		tree[k].r=merge(tree[x].r,tree[y].r,mid+1,r);
	}
	return k;
}
int query(int k,int l,int r,int x,int y)
{
	if (!k) return 0;
	if (l==x&&r==y) return tree[k].x;
	int mid=l+r>>1;
	if (y<=mid) return query(tree[k].l,l,mid,x,y);
	else if (x>mid) return query(tree[k].r,mid+1,r,x,y);
	else
	{
		int u=query(tree[k].r,mid+1,r,mid+1,y);
		if (u) return u;else return query(tree[k].l,l,mid,x,mid);
	}
}
struct SAM
{
	int n,son[N][26],fail[N],len[N],id[N],q[N],f[N],cnt,last;
	int newnode(){cnt++;memset(son[cnt],0,sizeof(son[cnt]));fail[cnt]=len[cnt]=0;return cnt;}
	void extend(int c)
	{
		int x=newnode(),p=last;last=x;len[x]=len[p]+1;id[len[x]]=x;
		while (!son[p][c]&&p) son[p][c]=x,p=fail[p];
		if (!p) fail[x]=1;
		else
		{
			int q=son[p][c];
			if (len[p]+1==len[q]) fail[x]=q;
			else
			{
				int y=newnode();
				len[y]=len[p]+1;
				memcpy(son[y],son[q],sizeof(son[q]));
				fail[y]=fail[q],fail[q]=fail[x]=y;
				while (son[p][c]==q) son[p][c]=y,p=fail[p];
			}
		}
	}
	void build(char *s)
	{
		cnt=0;last=1;newnode();n=strlen(s+1);
		for (int i=1;i<=n;i++) extend(s[i]-'a');
		for (int i=0;i<=n;i++) tmp[i]=0;
		for (int i=1;i<=cnt;i++) tmp[len[i]]++;
		for (int i=1;i<=n;i++) tmp[i]+=tmp[i-1];
		for (int i=1;i<=cnt;i++) q[tmp[len[i]]--]=i;
	}
	void run(char *s,int l,int r)
	{
		int m=strlen(s+1);
		int k=1,t=0;
		for (int i=1;i<=m;i++)
		{
			int c=s[i]-'a';
			while (!son[k][c]&&k) k=fail[k],t=len[k];
			if (!k) k=1,t=0;
			else k=son[k][c],t++;
			while (k)
			{
				int u=query(root[k],1,n,l,r);
				if (u-l+1<=len[fail[k]]) {k=fail[k],t=len[k];continue;}
				t=min(t,u-l+1);break;
			}
			if (!k) k=1,t=0;
			match[i]=t;
		}
	}
	void getright()
	{
		for (int i=1;i<=n;i++) ins(root[id[i]],1,n,i);
		for (int i=cnt;i>=1;i--)
		{
			int x=q[i];
			root[fail[x]]=merge(root[fail[x]],root[x],1,n);
		}
	}
	ll calc()
	{
		ll ans=0;
		for (int i=1;i<=cnt;i++) f[i]=N;
		for (int i=1;i<=n;i++) f[id[i]]=match[i];
		for (int i=cnt;i>=1;i--)
		{
			int x=q[i];
			ans+=max(0,len[x]-max(len[fail[x]],f[x]));
			f[fail[x]]=min(f[fail[x]],f[x]);
		}
		return ans;
	}
}S,T;
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	const char LL[]="%I64d\n";
#else
	const char LL[]="%lld\n";
#endif
	scanf("%s",s+1);S.build(s);S.getright();
	Q=read();
	while (Q--)
	{
		scanf("%s",s+1);
		int l=read(),r=read();
		S.run(s,l,r);
		T.build(s);printf(LL,T.calc());
	}
	return 0;
}