【CF316G3】Good Substrings
题意：给出n个限制(p,l,r)，我们称一个字符串满足一个限制当且仅当这个字符串在p中的出现次数在[l,r]之间。现在想问你S的所有本质不同的子串中，有多少个满足所有限制。
|S|,|p|<=10^5，n<=10。
题解：比较简单的后缀自动机题，我们先把原串和所有限制串放到一起建一个广义后缀自动机，然后在pre树上统计一下即可得到每个子串在每个限制串中出现了多少次。现在我们想知道原串中有多少满足条件的子串，即我们统计一下所有出现次数符合要求的，且在原串中出现过的点的贡献即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
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<len[i];j++)
extend(S[i][j]-'a'),s[last][i]++;
for(i=2;i<=tot;i++) add(pre[i],i);
dfs(1);
for(i=2;i<=tot;i++) if(s[i][0])
{
for(j=1;j<=n;j++) if(s[i][j]<L[j]||s[i][j]>R[j]) break;
if(j>n) ans+=(mx[i]-mx[pre[i]]);
}
printf("%d",ans);
return 0;
}