题目概述

CF316G3

解题报告

用广义后缀自动机做可以避免很多复杂的情况。

把 $s$ 和所有 $p$ 都扔进广义SAM里，然后把 $s$ 扔进SAM匹配得出所有属于 $s$ 的节点（注意 $fail$ 树传递）。

然后对于每个 $p$ ，把 $p$ 扔进SAM匹配每个前缀，完成后进行 $fail$ 树传递就可以得出SAM中每个节点在 $p$ 中的出现次数，得出满足条件的节点。

最后遍历 $fail$ 树，只有属于 $s$ 并且满足所有 $p$ 条件的节点才可以统计子串个数。

示例程序

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxk=10,maxn=50000,maxl=maxn*10,maxt=maxl<<1,maxi=26;

int K,pos[maxk+5],len[maxk+5],L[maxk+5],R[maxk+5];char A[maxn+5],s[maxl+5];
int pl,ro,son[maxt+5][maxi],fai[maxt+5],MAX[maxt+5];
vector<int> e[maxt+5];
int sum[maxt+5],cnt[maxt+5],ID;bool vis[maxt+5];
LL ans;

inline int newnode() {pl++;return pl;}
int Extend(int p,int c){
    if (son[p][c]){
        int q=son[p][c];if (MAX[p]+1==MAX[q]) return q;
        int nq=newnode();MAX[nq]=MAX[p]+1;for (int i=0;i<maxi;i++) son[nq][i]=son[q][i];
        fai[nq]=fai[q];fai[q]=nq;while (p && son[p][c]==q) son[p][c]=nq,p=fai[p];
        return nq;
    } else {
        int np=newnode();MAX[np]=MAX[p]+1;
        while (p && !son[p][c]) son[p][c]=np,p=fai[p];
        if (!p) {fai[np]=ro;return np;}
        int q=son[p][c];if (MAX[p]+1==MAX[q]) {fai[np]=q;return np;}
        int nq=newnode();MAX[nq]=MAX[p]+1;for (int i=0;i<maxi;i++) son[nq][i]=son[q][i];
        fai[nq]=fai[q];fai[q]=fai[np]=nq;while (p && son[p][c]==q) son[p][c]=nq,p=fai[p];
        return np;
    }
}
void DFS(int x) {for (auto u:e[x]) DFS(u),vis[x]|=vis[u];}
void Solve(int x){
    for (auto u:e[x]) Solve(u),sum[x]+=sum[u];
    if (L[ID]<=sum[x] && sum[x]<=R[ID]) cnt[x]++;
}
void Count(int x){
    if (vis[x] && cnt[x]==K) ans+=MAX[x]-MAX[fai[x]];
    for (auto u:e[x]) Count(u);
}
int main(){
    scanf("%s",A);
    ro=newnode();
    for (int i=0,p=ro;A[i];i++) p=Extend(p,A[i]-'a');
    scanf("%d",&K);
    for (int i=1,tot=0;i<=K;i++){
        pos[i]=tot;
        scanf("%s%d%d",s+pos[i],&L[i],&R[i]);
        len[i]=strlen(s+pos[i]);
        for (int j=0,p=ro;j<len[i];j++) p=Extend(p,s[pos[i]+j]-'a');
        tot+=len[i];
    }
    for (int i=2;i<=pl;i++) e[fai[i]].push_back(i);
    for (int i=0,p=ro;A[i];i++) p=son[p][A[i]-'a'],vis[p]=true;
    DFS(ro);
    for (int i=1;i<=K;i++){
        for (int j=1;j<=pl;j++) sum[j]=0;
        for (int j=0,p=ro;j<len[i];j++) p=son[p][s[pos[i]+j]-'a'],sum[p]++;
        ID=i;Solve(ro);
    }
    Count(ro);
    printf("%lld\n",ans);
    return 0;
}