P4770 [NOI2018] 你的名字 解题报告

先从 \(l=1,r=|s|\) 开始考虑

因为很难计算不重复的个数，考虑计算本质不同的与 \(s\) 的子串相同的个数，再用 \(t\) 中本质不同的子串数相减

因为涉及不同的子串数的计算以及匹配，所以可以对 \(s\) 和 \(t\) 都建立 SAM

接下来，因为 SAM 的 link 指针和 AC 自动机的 fail 指针很像，可以直接把 \(t\) 放到 \(s\) 的 SAM 上匹配

此时，我们就可以得到以 \(x\) 为结尾，长度最少为多少时才不重叠，记为 \(lim\)

记每个节点 endpos 集合中最大的字符串长度为 \(len\)，\(tag\) 表示该集合字符串第一次出现的结尾位置（因为集合里字符串互为后缀所以结尾相同)

统计答案时，parent 树上父亲的 \(len\) 一定不行，\(lim_tag\) 也不行，因为是后，会重，用 \(len_x\) 减去其中较大的就行了

接下来考虑加上 \(l\)，\(r\) 的限制，此时，在匹配时就不是每条路都能走了

用线段树维护后缀自动机的 endpos 集合，如果一个节点的 endpos 包含点 x，就将这个点对应线段树的对应位置改成1

因为 parent 树上的 endpos 是包含关系，可以合并

此时，在转移时判断要走到的点有没有 endpos 在区间 \([l,r]\) 即可

代码：

#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#define ll long long
using namespace std;
const int N=1000005,M=20000005;
int n,T,m;
string s,t;
struct SAM{
	int ch[26],link,len;
}s1[N];
int lst=1,tot=1,cnt[N],ids[N];
bool in[N];
void insert(int c)
{
	int p=lst,now=++tot;
	in[now]=1;
	s1[now].len=s1[lst].len+1;
	while(p&&!s1[p].ch[c])
	{
		s1[p].ch[c]=now;
		p=s1[p].link;
	}
	if(!p) s1[now].link=1;
	else
	{
		int q=s1[p].ch[c];
		if(s1[p].len+1==s1[q].len)
		{
			s1[now].link=q;
		}
		else
		{
			int clone=++tot;
			s1[clone]=s1[q];
			s1[clone].len=s1[p].len+1;
			while(p&&s1[p].ch[c]==q)
			{
				s1[p].ch[c]=clone;
				p=s1[p].link;
			}
			s1[q].link=s1[now].link=clone;
		}
	}
	lst=now; 
}
int rt[N],ls[M],rs[M],idx;
int update(int p,int l,int r,int x)
{
	if(!p) p=++idx;
	if(l==r)
	{
		return p;
	}
	int mid=(l+r)>>1;
	if(x<=mid) ls[p]=update(ls[p],l,mid,x);
	else rs[p]=update(rs[p],mid+1,r,x);
	return p;
}
int merge(int a,int b)
{
	if(!a||!b) return a+b;
	int p=++idx;
	ls[p]=merge(ls[a],ls[b]);
	rs[p]=merge(rs[a],rs[b]);
	return p;
}
bool query(int p,int l,int r,int ql,int qr)
{
	if(!p||ql>qr) return 0;
	if(ql<=l&&qr>=r) return 1;
	int mid=(l+r)>>1;
	if(ql<=mid&&query(ls[p],l,mid,ql,qr)) return 1;
	if(qr>mid&&query(rs[p],mid+1,r,ql,qr)) return 1;
	return 0;
}
struct sam{
	int ch[26],link,len;
	void clear()
	{
		for(int i=0;i<26;i++) ch[i]=0;
		len=link=0;
	}
}s2[N*2];
int lst1,tot1,tag[N*2],lim[N*2];
void init()
{
	for(int i=0;i<=tot1;i++)
	{
		s2[i].clear();
	}
	tot1=lst1=1;
}
void ins(int c)
{
	int p=lst1,now=++tot1;
	s2[now].len=tag[now]=s2[p].len+1;
	while(p&&!s2[p].ch[c])
	{
		s2[p].ch[c]=now;
		p=s2[p].link;
	}
	if(!p) s2[now].link=1;
	else
	{
		int q=s2[p].ch[c];
		if(s2[p].len+1==s2[q].len)
		{
			s2[now].link=q;
		}
		else
		{
			int clone=++tot1;
			s2[clone]=s2[q];
			s2[clone].len=s2[p].len+1;
			tag[clone]=tag[q];
			while(p&&s2[p].ch[c]==q)
			{
				s2[p].ch[c]=clone;
				p=s2[p].link;
			}
			s2[q].link=s2[now].link=clone;
		}
	}
	lst1=now;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>s;
	n=s.size();
	s=" "+s;
	for(int i=1;i<=n;i++) insert(s[i]-'a');
//	printf("%d ",tot);
	for(int i=1;i<=tot;i++)
	{
		cnt[s1[i].len]++;
//		printf("%d ",s1[i].len);
	}
	for(int i=1;i<=tot;i++) cnt[i]+=cnt[i-1];
	for(int i=1;i<=tot;i++) ids[cnt[s1[i].len]--]=i;
	for(int i=tot;i>0;i--)
	{
		int x=ids[i];
//		cout<<in[x]<<" "<<x<<'\n';
		if(in[x]) rt[x]=update(rt[x],1,n,s1[x].len);
		rt[s1[x].link]=merge(rt[s1[x].link],rt[x]);
	}
	cin>>T;
	while(T--)
	{
		int l,r;
		cin>>t>>l>>r;
		m=t.size();
		t=" "+t;
		init();
		int p=1,len=0;
		for(int i=1;i<=m;i++)
		{
			int c=t[i]-'a';
			ins(c);
			while(1)
			{
				if(s1[p].ch[c]&&query(rt[s1[p].ch[c]],1,n,l+len,r))
				{
					len++,p=s1[p].ch[c];
					break;
				}
				if(len==0) break;
				len--;
				if(len==s1[s1[p].link].len)
				p=s1[p].link;
			}
			lim[i]=len;
		}
		ll ans=0;
		for(int i=2;i<=tot1;i++)
		{
			ans=ans+max(0,s2[i].len-max(s2[s2[i].link].len,lim[tag[i]]));
		}
		cout<<ans<<'\n';
	}
	return 0;
}