HDU 3065 AC自动机

发表于 | 分类于 | 阅读次数：

算是比较简单的AC自动机题目，但是还是有很多细节需要注意！

题目链接

注意的地方

在从源码中进行查找的时候，如果是大写字母，可以直接跳过，但是注意令root = 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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <bitset>
#include <string>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define eps 1e-8
#define PI acos(-1.0)
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 1005;
struct node{
   char s[51];
   int cnt;
   int pos;
}a[maxn];
const int kind = 130;
int num[1005], vis[100005],mark[100005],nxt[100005][130], fail[100005];
int cnt;
int newnode()
{
    ++cnt;
    for(int i = 0; i < kind; ++i)
    {
        nxt[cnt][i] = -1;
    }
    vis[cnt] = 0;
    mark[cnt] = 0;
    return cnt;
}

void init(){
   cnt = -1;
   newnode();
}


void word_insert(char s[], int pos)
{
    int sz = strlen(s);
    int now = 0;
    for(int i = 0; i < sz; ++i)
   {
     int tmp = s[i];
     if(nxt[now][tmp] == -1)
     nxt[now][tmp] = newnode();
     now = nxt[now][tmp];
   }
   mark[now] = pos;
}

void build()
{
    fail[0] = 0;
    queue<int>Q;
    for(int i = 0 ; i < kind; ++i)
    {
        if(nxt[0][i] == -1)
            nxt[0][i] = 0;
        else{
            fail[nxt[0][i]] = 0;
            Q.push(nxt[0][i]);
        }
    }
    while(!Q.empty())
    {
        int now = Q.front();
        Q.pop();
        for(int i = 0; i < kind; ++i)
        {
            if(nxt[now][i] == -1)
                nxt[now][i] = nxt[fail[now]][i];
            else{
                fail[nxt[now][i]] = nxt[fail[now]][i];
                Q.push(nxt[now][i]);
            }
        }
    }
}

char s[2000005];

void ac_auto(char s[])
{
    int sz = strlen(s);
    int now = 0;
    for(int i = 0; i < sz; ++i)
    {
        if(s[i] < 'A' || s[i] > 'Z') {now = 0; continue;}
        now = nxt[now][s[i]];
        int tmp = now;
        while(tmp != 0)
        {
            num[mark[tmp]]++;
            tmp = fail[tmp];
        }
    }
}

int main()
{
    int n;
    while(scanf("%d",&n) != EOF){
    init();
    for(int i = 1; i <= n; ++i)
    {
        scanf("%s",a[i].s);
        a[i].pos = i;
        a[i].cnt = 0;
        num[i] = 0;
        word_insert(a[i].s, a[i].pos);
    }
    build();
    scanf("%s",s);
    ac_auto(s);
    for(int i = 1; i <= n; ++i)
    {
        if(num[a[i].pos] > 0)
        {
           printf("%s: %d\n",a[i].s ,num[a[i].pos]);
        }
    }
    }
}