CF 316G3 Good Substrings——广义后缀自动机

时间:2022-02-26 17:10:49

题目:http://codeforces.com/contest/316/problem/G3

对询问串和模式串一起建一个后缀自动机,做出在每个串上的 right 集合大小之后枚举自动机上的每个点看看是否合法即可(合法的话,贡献是 len[ cr ] - len[ fa ])。

注意做出拓扑序后用的是 q[ i ] 而不是 i !

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=,M=,K=;
int n,cnt=,len[N],fa[N],go[N][K],ep[N];
int l[M],r[M],tx[N],q[N],ct[N][M]; ll ans;
char s[N]; bool vis[N];
int cz(int p,int w,int bh)
{
int q=go[p][w], nq=++cnt; len[nq]=len[p]+;
fa[nq]=fa[q]; fa[q]=nq;
memcpy(go[nq],go[q],sizeof go[q]);
for(;go[p][w]==q;p=fa[p])go[p][w]=nq;
return nq;
}
int ins(int p,int w,int bh)
{
if(go[p][w])
{
int q=go[p][w];
if(len[q]==len[p]+)return q;
return cz(p,w,bh);
}
int np=++cnt; len[np]=len[p]+;
for(;p&&!go[p][w];p=fa[p])go[p][w]=np;
if(!p){fa[np]=;return np;}
int q=go[p][w]; if(len[q]==len[p]+)fa[np]=q;
else fa[np]=cz(p,w,-);
return np;
}
void Rsort()
{
for(int i=;i<=cnt;i++)tx[len[i]]++;
for(int i=;i<=cnt;i++)tx[i]+=tx[i-];
for(int i=;i<=cnt;i++)q[tx[len[i]]--]=i;
}
bool chk(int cr)
{
for(int i=;i<=n;i++)
if(ct[cr][i]<l[i]||ct[cr][i]>r[i])
return false;
return true;
}
int main()
{
scanf("%s",s+); int d=strlen(s+);
for(int i=,p=;i<=d;i++)
p=ins(p,s[i]-'a'+,), ct[p][]=;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%s%d%d",s+,&l[i],&r[i]);
d=strlen(s+);
for(int j=,p=;j<=d;j++)
p=ins(p,s[j]-'a'+,i), ct[p][i]=;
}
Rsort();
for(int i=cnt;i;i--)
{
int cr=q[i], f=fa[q[i]];////q[i] not i!!!
for(int j=;j<=n;j++)ct[f][j]+=ct[cr][j];
}
for(int i=;i<=cnt;i++)
if(ct[i][]&&chk(i))
ans+=len[i]-len[fa[i]];
printf("%lld\n",ans);
return ;
}