[Bzoj3172][Tjoi2013]单词（fail树）

3172: [Tjoi2013]单词

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 4777 Solved: 2345
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

a

aa

aaa

Sample Output

HINT

分析：

fail树裸题，为什么我一开始会分析成parent树。。

AC代码：

# include <cstdio>

# include <cstring>

# include <iostream>

using namespace std;

const int N = 1e6 + ;

int ch[N][],cnt,fail[N],n,id[],w[N];char str[N];

int insert(char s[])

{

    int p = ,v,len = strlen(s);

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

    {

        v = s[i] - 'a';

        if(!ch[p][v])ch[p][v] = ++cnt;

        p = ch[p][v];

        w[p]++;

    }

    return p;

}

int que[N];

void bfs_fail()

{

    int h = ,t = ,u,g;

    for(int i = ;i < ;i++)if(ch[][i])que[t++] = ch[][i];

    while(h != t)

    {

        u = que[h++];

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

        {

            int &v = ch[u][i];g = ch[fail[u]][i];

            if(!v){v = g;continue;}

            fail[que[t++] = v] = g;

        }

    }

    for(int i = h - ;~i;i--)w[fail[que[i]]] += w[que[i]];

}

int main()

{

  scanf("%d",&n);

  for(int i = ;i <= n;i++)scanf("%s",str),id[i] = insert(str);

  bfs_fail();

  for(int i = ;i <= n;i++)printf("%d\n",w[id[i]]);

}

秒客网