【CF316G3】Good Substrings

题意：给出n个限制(p,l,r)，我们称一个字符串满足一个限制当且仅当这个字符串在p中的出现次数在[l,r]之间。现在想问你S的所有本质不同的子串中，有多少个满足所有限制。

|S|,|p|<=10^5，n<=10。

题解：比较简单的后缀自动机题，我们先把原串和所有限制串放到一起建一个广义后缀自动机，然后在pre树上统计一下即可得到每个子串在每个限制串中出现了多少次。现在我们想知道原串中有多少满足条件的子串，即我们统计一下所有出现次数符合要求的，且在原串中出现过的点的贡献即可。

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N=1100010;int n,cnt,tot,last,ans;int len[11],L[11],R[11],s[N][11],ch[N][26],pre[N],mx[N],to[N],nxt[N],head[N],ml[N];char S[11][50010];inline void extend(int x){	int p=last;	if(ch[p][x])	{		int q=ch[p][x];		if(mx[q]==mx[p]+1)	last=q;		else		{			int nq=++tot;			pre[nq]=pre[q],pre[q]=nq,mx[nq]=mx[p]+1,last=nq;			memcpy(ch[nq],ch[q],sizeof(ch[q]));			for(;p&&ch[p][x]==q;p=pre[p])	ch[p][x]=nq;		}	}	else	{		int np=++tot;		last=np,mx[np]=mx[p]+1;		for(;p&&!ch[p][x];p=pre[p])	ch[p][x]=np;		if(!p)	pre[np]=1;		else		{			int q=ch[p][x];			if(mx[q]==mx[p]+1)	pre[np]=q;			else			{				int nq=++tot;				pre[nq]=pre[q],pre[q]=pre[np]=nq,mx[nq]=mx[p]+1;				memcpy(ch[nq],ch[q],sizeof(ch[q]));				for(;p&&ch[p][x]==q;p=pre[p])	ch[p][x]=nq;			}		}	}}inline void add(int a,int b){	to[cnt]=b,nxt[cnt]=head[a],head[a]=cnt++;}void dfs(int x){	for(int i=head[x],j;i!=-1;i=nxt[i])	{		dfs(to[i]);		for(j=0;j<=n;j++)	s[x][j]+=s[to[i]][j];	}}int main(){	scanf("%s%d",S[0],&n),len[0]=strlen(S[0]);	int i,j;	last=tot=1;	memset(head,-1,sizeof(head));	for(i=1;i<=n;i++)	scanf("%s%d%d",S[i],&L[i],&R[i]),len[i]=strlen(S[i]);	for(i=0;i<=n;i++)		for(last=1,j=0;j
         
          R[j])	break;		if(j>n)	ans+=(mx[i]-mx[pre[i]]);	}	printf("%d",ans);	return 0;}