洛谷P3966/TJOI2013 单词

@Pelom  October 31, 2019

题意

给出$n$个单词,求每个单词共出现几次

数据范围:单词总长度$\le 10^6$

题解

多模匹配,使用$\text{AC}$自动机解决
需要注意的是,可能出现重复的单词;为避免字典树的值被覆盖,只记录第一个编号,而将其他相同的单词指向这个编号
统计答案时,在该前缀的所有后缀上($\text{Fail}$树上的祖先节点上),将其自身答案累加上去,就是总共出现的次数

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1000010;
int n;
char s[210][N];
int ans[210],sm[210];
struct AC{
    queue<int> Q;
    int trie[N][26],fail[N],w[N],ed[N],cnt;
    bool vis[N];
    inline void insert(int x){
        int l=strlen(s[x]+1);
        int u=0;
        for(int i=1;i<=l;i++){
            int v=s[x][i]-'a';
            if(!trie[u][v])
                trie[u][v]=++cnt;
            u=trie[u][v];
            w[u]++;
        }
        if(ed[u])
            sm[x]=ed[u];
        else ed[u]=x;
    }
    inline void getFail(){
        for(int i=0;i<26;i++)
            if(trie[0][i])
                Q.push(trie[0][i]);
        for(;!Q.empty();){
            int u=Q.front();
            Q.pop();
            for(int i=0;i<26;i++)
                if(trie[u][i]){
                    fail[trie[u][i]]=trie[fail[u]][i];
                    Q.push(trie[u][i]);
                }
                else trie[u][i]=trie[fail[u]][i];
        }
    }
    inline void query(int x){
        int l=strlen(s[x]+1);
        int u=0;
        for(int i=1;i<=l;i++){
            int v=s[x][i]-'a';
            u=trie[u][v];
            for(int j=u;j;j=fail[j])
                if(ed[j] && !vis[u])
                    ans[ed[j]]+=w[u];
            vis[u]=1;
        }
    }
} ac;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s[i]+1);
        ac.insert(i);
    }
    ac.getFail();
    for(int i=1;i<=n;i++)
        if(!sm[i])
            ac.query(i);
    for(int i=1;i<=n;i++)
        if(!sm[i])
            printf("%d\n",ans[i]);
        else printf("%d\n",ans[sm[i]]);
    return 0;
}

添加新评论