[TJOI2013]单词

冷不防 2021-12-21 15:25 287阅读 0赞

## **Description** ##

某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次

## **Input** ##

第一个一个整数N,表示有多少个单词，接下来N行每行一个单词。每个单词由小写字母组成，N<=200,单词长度不超过10^6

## **Output** ##

输出N个整数，第i行的数字表示第i个单词在文章中出现了多少次。

## **Solution** ##

乍一看，这是一道AC自动机的板子题，只要把AC自动机建好，再来匹配就好了

然后，你就WA了。。。

为什么呢？

我们发现，它的输入单词里是会有相同的单词的，所以当成板子题来做的话，就会由于建tire树的覆盖而导致答案出错，那么怎么来解决这个问题呢？

我们定义一个same数组，end数组只记录最早的编号，每次如果要覆盖，便把令该节点的same值为这个位置上的end的值，查询时每个都查询一遍，输出答案就输出ans\[same\[i\]\]

你兴冲冲的码完之后，提交，本以为能够AC，结果，在你A了9个点之后，TLE。。。

怎么办呢？

既然有重复的，那么我们显然不需要把每个都扫一遍，而是只扫一次，再通过现有的答案来得出正确答案，我们只需要解决如何扫描一次后的答案来得出正确答案就可以了

定义两个数组，apr和vis，apr记录在AC自动机上每一个节点被覆盖的次数，vis记录当前节点在统计答案时有没有被扫过。

在统计答案时，若当前节点是某个单词的末尾且没有被扫过，说明它能够为该单词有贡献，就将该单词的答案加上apr\[now\]。每次扫到AC自动机上的一个节点，就把它的vis标记变成1，这样子就能得出正确答案了，详见代码。

## **Code:** ##

#include<bits/stdc++.h>
    #define N 100001
    using namespace std;
    int n,cnt,Len,ans[201];
    char ch[201][N];
    namespace AC_Automaton{
        queue<int> q;
        int same[N],apr[N*27],vis[N*27];
        int trie[N*27][26],ed[N*27],fail[N*27];
        void ins(int x){
            int now=0,len=strlen(ch[x]+1);
            for(int i=1;i<=len;i++){
                int num=ch[x][i]-'a';
                if(!trie[now][num]) trie[now][num]=++cnt;
                now=trie[now][num];apr[now]++;
            }
            if(ed[now]) same[x]=ed[now];
            else ed[now]=x;
        }
        void makefail(){
            for(int i=0;i<26;i++)
                if(trie[0][i]) q.push(trie[0][i]);
            while(!q.empty()){
                int x=q.front();q.pop();
                for(int i=0;i<26;i++)
                    if(trie[x][i]) fail[trie[x][i]]=trie[fail[x]][i],q.push(trie[x][i]);
                    else trie[x][i]=trie[fail[x]][i];
            }
        }
        void query(char *s){
            int now=0,len=strlen(s+1);
            for(int i=1;i<=len;i++){
                int num=s[i]-'a';
                now=trie[now][num];
                for(int j=now;j;j=fail[j])
                    if(ed[j]&&!vis[now]) ans[ed[j]]+=apr[now];
                vis[now]=1;
            }
        }
    }
    int main(){
        scanf("%d",&n);  
        using namespace AC_Automaton; 
        for(int i=1;i<=n;i++){
            scanf("%s",ch[i]+1);
            ins(i);
        }
        makefail();
        for(int i=1;i<=n;i++)
            if(!same[i]) query(ch[i]);
        for(int i=1;i<=n;i++)
           if(!same[i]) printf("%d\n",ans[i]);
           else printf("%d\n",ans[same[i]]);
        return 0;
    }

转载于:https://www.cnblogs.com/NLDQY/p/10254593.html