BZOJ_3172_[Tjoi2013]单词

BZOJ_3172_[Tjoi2013]单词_AC自动机

Description

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

Input

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

Output

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

Sample Input

3
a
aa
aaa

Sample Output

6
3
1

对所有串建立trie图，插入时对沿途所有经过的点标记++。

然后在fail树上求每个子串对应位置的子树标记和即可。

由于bfs拓展是按层拓展，所以这里直接倒着扫一遍队列。

代码：

#include <cstdio>

#include <string.h>

#include <algorithm>

using namespace std;

#define N 1000050

int ch[N][26],cnt=1,fail[N],flg[N],n,Q[N],l,r,pos[N];

char w[N];

void insert(int x) {

    int i,p=1;

    for(i=1;w[i];i++) {

        int &k=ch[p][w[i]-'a'];

        if(!k) k=++cnt;

        p=k;

        flg[p]++;

    }

    pos[x]=p;

}

void build() {

    int i;

    for(i=0;i<26;i++) ch[0][i]=1;

    Q[r++]=1;

    while(l<r) {

        int p=Q[l++];

        for(i=0;i<26;i++) {

            if(ch[p][i]) fail[ch[p][i]]=ch[fail[p]][i],Q[r++]=ch[p][i];

            else ch[p][i]=ch[fail[p]][i];

        }

    }

}

int main() {

    scanf("%d",&n);

    int i;

    for(i=1;i<=n;i++) {

        scanf("%s",w+1);

        insert(i);

    }

    build();

    for(i=cnt;i;i--) flg[fail[Q[i]]]+=flg[Q[i]];

    for(i=1;i<=n;i++) {

        printf("%d\n",flg[pos[i]]);

    }

}

巴特西