SDNUOJ 1118 单词统计(AC自动机)

Description

给定一个字符串和若干个单词，统计这些单词在这个字符串中出现的次数。

题目链接： http://www.acmicpc.sdnu.edu.cn/problem/show/1118

Sample Input1

5
a
ab
ba
aba
bab
aababa
1
2
3
4
5
6
7

Sample Output1

4 2 2 2 1

Sample Input2(可能卡的样例)

3
aa
aa
aa
aaa
1
2
3
4
5

Sample Output2

2 2 2

AC自动机

巧妙的数据结构（Trie） + 灵活的算法（KMP) = 巧妙灵活的算法(AC自动机)

真的是，二者结合地天衣无缝

By the way

Trie里有个sum[N]数组是统计输入(Input)里单词重复出现次数的

此题询问最后给出的长字符串中输入(Input)的每个字符串出现次数的

好像说的不清楚，反正知道有那么两个东西不是一回事就行

Analyze

此题要在主串里查询每个输入串(可能重复)出现次数

用上Trie中的is[N]数组标记每个字符串结束处结点

开一个fro[N]数组记录答案（每个字符串出现次数）

最后遍历结点数(cnt)，剔除(is[i] == 0)的fro[i]，输出剩下的(本来就是有序的)

这个时候开始WA了，因为没处理像上方Input2那样的情况

我想了一个办法（我竟然能在一个较陌生的算法上搞小动作！！！）：

开一个amount[n]数组，记录每个输入字符串尾字母后的结束结点

最后只需要遍历输入串数(amo)一个个输出：

for(int i = 0; i < amo; ++i)
            printf("%d%c", fro[ amount[i] ], i == amo - 1 ? '\n' : ' ');
1
2

Code

#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N =  5 * 1e5 + 9;

bool is[N];
int cnt = 0, amo = 0, fail[N], fro[N], trie[N][26];
int amount[10005];

void clean(int num)
{
    fail[num] = 0, fro[num] = 0;
    memset(trie[num], 0, sizeof(trie[num]));
}

void plug(char * s)
{
    int root = 0;
    for(int i = 0; s[i]; ++i)
    {
        int x = s[i] - 'a';
        if(!trie[root][x])
        {
            ++cnt;
            clean(cnt);
            trie[root][x] = cnt;
        }
        root = trie[root][x];
    }
    is[root] = 1;
///    sum[root]++;统计单词在树中出现次数
    amount[amo++] = root;
}

void getfail()
{
    queue<int> q;
    for(int i = 0; i < 26; ++i)
        if(trie[0][i])
            fail[ trie[0][i] ] = 0, q.push(trie[0][i]);

    while(!q.empty())
    {
        int now = q.front();
        q.pop();

        for(int i = 0; i < 26; ++i)
        {
            if(trie[now][i])
            {
                fail[ trie[now][i] ] = trie[ fail[now] ][i];
                q.push(trie[now][i]);
            }
            else
                trie[now][i] = trie[ fail[now] ][i];
        }
    }
}

void query(char * s)
{
    int now = 0, len = strlen(s);
    for(int i = 0; i < len; ++i)
    {
        now = trie[now][ s[i] - 'a' ];
        for(int j = now; j ; j = fail[j])
            if(is[j])
                fro[j]++;
    }
}

char s[1000005];

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        cnt = 0, amo = 0;
        memset(is, 0, sizeof(is));
        memset(amount, 0, sizeof(amount));
        clean(0);
        for(int i = 0; i < n; ++i)
        {
            scanf("%s", s);
            plug(s);
        }
        getfail();
        scanf("%s", s);
        query(s);
        for(int i = 0; i < amo; ++i)
            printf("%d%c", fro[ amount[i] ], i == amo - 1 ? '\n' : ' ');
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103