2023CCPC女生专场 L 字符串游戏【AC自动机】

一句话题解：AC自动机，在fail树上自顶向下预处理，以实现O(1)统计答案

Description:

n个模式串{Sn}，1个文本串T。每次小B会选取T的一个子串（只要子串位置不相同则视作不同），对答案的贡献是该子串中含有的模式串的总数目。对于选取子串的所有方法，求总共的答案。

Solution:

对于文本串出现的任何一个模式串，假设它的位置是\([T_l,T_{l+1},...,T_r]\)，则对答案的贡献是\(l*(len_T-r+1)\)

暴力的想法是：对模式串建立Trie树，枚举文本串T的每一个位置作为起始位置，在Trie树上匹配，找到模式串就累计答案。

由于是多模式匹配问题，考虑AC自动机。对模式串建立AC自动机，对于文本串T的每一个位置，在AC自动机上查找，由于查找的是T的前缀的不同后缀，所以结束位置\(T _r\)是不变的，则答案的贡献

\(\sum [l_i*(len_T-r+1)]\\=(\sum l_i)*(len_T-r+1)\\=[\sum (r-len_{s_i}+1)]*(len_T-r+1)\\=[(r+1)\sum1-\sum len_{s_i}]*(len_T-r+1)\)

（注意上面的式子建立在字符串的下标从1开始的基础上）。

所以，只需要统计每个结点能跳到的fail结点的数量\(\sum 1\)，以及len的总和\(\sum len_i\)，就可以\(O(1)\)得到以T的某一个位置结尾的所有答案。

将fail看作父亲结点，则能跳到的所有的fail结点就是所有的祖先结点，则预处理出所有的\(\sum 1\)和\(\sum len_i\)复杂度是\(O(\sum len_s)\)的。

综上所述，时间复杂度是\(O(\sum|S|*N+|T|)\)，\(N\)是字符集大小。

Little Insight: 在AC自动机的拓扑排序优化中，答案是在fail树上自底向上统计的；在本题中，先从上到下预处理，贡献统一在最深的结点加上。

Code:

//AC自动机，在fail树上自顶向下预处理，以实现O(1)统计答案
//by dttttttt
//2023/10/27
#include<iostream>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
const int N=2e5+5,M=1e6+5,mod=1e9+7;
int n,m,tot;
string s[N],t[M];
struct node{
    int to[30];
    int fail,end;
    int s_num; //存\sum 1
    ll s_len; //存\sum len
    vector<int> fail_to; //fail树上的子节点
}ac[N];
void build_trie(){
    for(int j=1;j<=n;++j){
        int cur=0;
        int len_j=s[j].length();
        for(int i=0;i<len_j;++i){
            int c=s[j][i]-'a';
            if(ac[cur].to[c]==0) ac[cur].to[c]=++tot;
            cur=ac[cur].to[c];
        }
        ac[cur].end=s[j].length();
    }
}
void build_fail(){
    queue<int>q;
    ac[0].fail=0;
    for(int i=0;i<26;++i)
        if(ac[0].to[i]){
            ac[ac[0].to[i]].fail=0;
            ac[0].fail_to.push_back(ac[0].to[i]);
            q.push(ac[0].to[i]);
        }
    
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=0;i<26;++i){
            if(ac[u].to[i]){
                ac[ac[u].to[i]].fail=ac[ac[u].fail].to[i];
                q.push(ac[u].to[i]);//这里老是忘写
                ac[ac[ac[u].fail].to[i]].fail_to.push_back(ac[u].to[i]);
            }
            else{
                ac[u].to[i]=ac[ac[u].fail].to[i];
                //ac[ac[ac[u].fail].to[i]].fail_to.push_back(ac[u].to[i]); 这里不需要！
            }
        }
    }
}
void dfs_fail(int u,int num,ll len){
    if(ac[u].end){
        num+=1;
        len+=ac[u].end;
        len%=mod;
    }
    ac[u].s_num=num;
    ac[u].s_len=len;
    for(int v:ac[u].fail_to){
        dfs_fail(v,num,len);
    }
}

int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>s[i];
    for(int i=1;i<=m;++i) cin>>t[i];

    build_trie();
    build_fail();

    dfs_fail(0,0,0); //dfs fail树预处理

    for(int j=1;j<=m;++j){
        int len_t=t[j].length();
        int cur=0;
        ll ans=0;
        for(int i=0;i<len_t;++i){
            int c=t[j][i]-'a';
            cur=ac[cur].to[c];
            ans+=1ll*(len_t-i)*((1ll*(i+2)*ac[cur].s_num%mod-ac[cur].s_len+mod)%mod)%mod;
            ans%=mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}