题解 CF1202E 【You Are Given Some Strings...】

· · 题解

洛谷的L^AT_EX可能挂，请在My blog查看

CF1202E

题意：给一个串T和n个串s_i.定义f(T,s)表示s在T中的出现次数。

求\sum_{i=1}^n\sum_{j=1}^nf(T,s_i+s_j). 数据范围：|T|,\sum_{i=1}|s_i|\le 2\times 10^5

<!--more-->

解：考虑枚举划分点x，该点及之前为s_i,该点之后为s_j,统计一下s_i,s_j的数量f1(x),f2(x+1)然后乘法原理相乘即可。

具体如何统计？该问题等价于，给一个文本串和一些模式串，要对文本串的每个前缀求出有多少模式串是他的后缀（后面那个只要把串反转就好） 文本串长度至多2e5,模式串长度和至多2e5.
对模式串建AC自动机，考虑fail指针指向的是根到当前串的最长后缀。而所求等价于为模式串的后缀的数量，因此通过fail求和即可。

时间复杂度为线性。

#define MAXN 400011
struct ACAM
{
    ll t[MAXN][26],val[MAXN],fail[MAXN],vis[MAXN];//val[u]表示点根到u的串的为模式串的后缀数量
    ll cnt=0;
    void insert(char* a,ll n)
    {
        ll u=0;
        for(ll i=1;i<=n;++i)
        {
            ll &v=t[u][a[i]-'a'];
            if(!v)v=++cnt;
            u=v;
        }
        ++val[u];
    }
    void build()//建AC自动机并求val
    {
        std::queue<ll>q;
        for(ll i=0;i<26;++i)
            if(t[0][i])q.push(t[0][i]);
        while(!q.empty())
        {
            ll u=q.front();q.pop();
            for(ll i=0;i<26;++i)
            {
                ll &v=t[u][i];
                if(v)fail[v]=t[fail[u]][i],val[v]+=val[fail[v]],q.push(v);
                else v=t[fail[u]][i];
            }
        }
    }
    void Query(char* a,ll n,ll f[])//求f
    {
        for(ll i=0;i<=cnt;++i)vis[i]=0;
        ll u=0;
        for(ll i=1;i<=n;++i)
        {
            u=t[u][a[i]-'a'];
            f[i]=val[u];
        }
    }
}ac,Rac;//ac自动机和反串的ac自动机
ll f1[MAXN],f2[MAXN];
char a[MAXN],b[MAXN];
int main()
{
    scanf("%s",a+1);
    ll n=read(),la=strlen(a+1);
    while(n--)
    {
        scanf("%s",b+1);
        ll lb=strlen(b+1);
        ac.insert(b,lb);//插入ac自动机
        std::reverse(b+1,b+lb+1);Rac.insert(b,lb);
    }
    ac.build();Rac.build();
    ac.Query(a,la,f1);std::reverse(a+1,a+la+1);Rac.Query(a,la,f2);
    ll ans=0;
    for(ll i=1;i<=la;++i)
    {
        ans+=f1[i]*f2[la-i];//注意这里的f2没有反转，如果反转了就应该是f1[i]*f2[i+1]
    }
    printf("%lld",ans);
    return 0;
}