【BZOJ-3172】单词 AC自动机

3172: [Tjoi2013]单词

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 2567 Solved: 1200
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

3
a
aa
aaa

Sample Output

6
3
1

HINT

Source

Solution

ACMachine模板题，而且不用匹配.

建Trie树，构建Fail指针，在构建Fail指针的过程中，累加一下次数即可

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

#define N 1000010

int sz,son[N][],fail[N],q[N],sum[N],loc[N];

int n; char s[N];

void clear()

{

    sz=;

    for (int i=; i<; i++) son[][i]=;

}

void insert(int &pos)

{

    int x=;

    for (int i=; i<strlen(s); i++)

        {

            if (!son[x][s[i]-'a']) son[x][s[i]-'a']=++sz;

            x=son[x][s[i]-'a']; sum[x]++;

        }

    pos=x;

}

void buildfail()

{

    int head=,tail=; q[]=; fail[]=;

    while (head<tail)

        {

            int now=q[head++];

            for (int i=; i<; i++)

                {

                    if (!son[now][i]) continue;

                    int ff=fail[now];

                    while(!son[ff][i]) ff=fail[ff];

                    fail[son[now][i]]=son[ff][i];

                    q[tail++]=son[now][i];

                }

        }

     for (int i=tail-; i>=; i--)

         sum[fail[q[i]]]+=sum[q[i]];

}

int main()

{

    clear();

    scanf("%d",&n);

    for (int i=; i<=n; i++)

        scanf("%s",s),insert(loc[i]);

    buildfail();

    for (int i=; i<=n; i++)

        printf("%d\n",sum[loc[i]]);

    return ;

}

很早以前做的题了，那时候用自动机，出现奇怪的错误...interesting...MDZZ

秒客网