题解归档 - cf1202E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf1202E
• 本地来源：problems/cf1202E/idea.md
• 题目链接：https://codeforces.com/contest/1202/problem/E
• 原始标题：CF1202E — You Are Given Some Strings...

思路

CF1202E — You Are Given Some Strings...

题意

给定文本 t 与 n 个串 s_i，求
[\sum_{i=1}^{n}\sum_{j=1}^{n} f(t,\, s_i+s_j)]
其中 f(t,s) 为 s 在 t 中出现次数（可重叠）。相同拼接串来自不同 (i,j) 仍分别计数。

做法

每个 s_i+s_j 在 t 中的出现对应唯一切分点：左半是 s_i 的匹配后缀，右半是 s_j 的匹配前缀。

• 正向 AC：所有 s_i 建自动机，扫 t 得 g0[p] = 以位置 p 结尾的 s_i 匹配总数（含重复串）。
• 反向 AC：所有 reverse(s_i) 建自动机，扫 reverse(t) 得 g[p] = 以位置 p 在反串中结尾的匹配数，即原串中以某位置开头的 s_i 前缀匹配数。

答案：(\sum_{p=1}^{|t|-1} g0[p]\cdot g[|t|-p])。

实现要点

• f[u] 沿 fail 链累加，扫描时 g[i]=f[u] 即后缀匹配计数。
• 总长度 (\sum|s_i|\le 2\cdot 10^5)，Trie 结点 (\le 2\cdot 10^5)，maxn=200005 足够且省内存。
• 需 long long 累加答案。

本地验证

• 样例 + stress.py 200~500 组对拍通过。
• 第 1 次提交 WA（passedTestCount=0，内存约 104MB）：原 maxn=400005 数组过大；已缩小并去掉调试输出后重交。

代码

来源：problems/cf1202E/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:53:10
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
ll ch[maxn+5][26],fa[maxn+5],f[maxn+5],g[maxn+5],g0[maxn+5],ptr,n,lt,ans;
string t,p,ss[maxn+5];
queue<ll>q;
void ac_init(){
    while(!q.empty()) q.pop();
    for(lli=0;i<=ptr;i++){
        f[i]=0,fa[i]=0;
        for(llj=0;j<26;j++) ch[i][j]=0;
    }
    ptr=0;
}
void ac_add(string s){
    ll u=0,c;
    for(lli=0;i<(ll)s.size();i++){
        c=s[i]-'a';
        if(!ch[u][c]) ch[u][c]=++ptr;
        u=ch[u][c];
    }
    f[u]++;
}
void ac_build(){
    for(lli=0;i<26;i++) if(ch[0][i]){
        fa[ch[0][i]]=0;
        q.push(ch[0][i]);
    }
    while(!q.empty()){
        ll u=q.front();
        q.pop();
        for(lli=0;i<26;i++){
            if(ch[u][i]){
                fa[ch[u][i]]=ch[fa[u]][i];
                f[ch[u][i]]+=f[fa[ch[u][i]]];
                q.push(ch[u][i]);
            }else ch[u][i]=ch[fa[u]][i];
        }
    }
}
void ac_scan(string s){
    ll u=0,c;
    for(lli=0;i<(ll)s.size();i++){
        c=s[i]-'a';
        u=ch[u][c];
        g[i+1]=f[u];
    }
}
int main(){
    ll i;
    cin>>t>>n;
    lt=t.size();
    for(i=0;i<n;i++) cin>>ss[i];
    ac_init();
    for(i=0;i<n;i++) ac_add(ss[i]);
    ac_build();
    ac_scan(t);
    for(i=1;i<=lt;i++) g0[i]=g[i];
    ac_init();
    for(i=0;i<n;i++){
        string p=ss[i];
        reverse(p.begin(),p.end());
        ac_add(p);
    }
    ac_build();
    string p=t;
    reverse(p.begin(),p.end());
    ac_scan(p);
    ans=0;
    for(i=1;i<lt;i++) ans+=g0[i]*g[lt-i];
    cout<<ans<<"\n";
    return 0;
}