HDU2222 Keywords Search AC自动机

每次第一道模板题都是非常有意义的,考试前夕费尽心思学了KMP,学了Trie树,就是为了学这个做铺垫的,这道题时著名的AC自动机模板题。个人理解AC自动机就是在一棵Trie树上求失配指针,然后实现了多模匹配。只需遍历一次文本串就能求出所有的内容。在下面的query代码里,因为不能重复计算相同的模板串,所以每次加上后temp->count=-1,表示已经算过,在while循环里temp->count!=-1的时候才进行失配其实是有意义的,当temp->count==-1时说明已经沿着失配指针匹配过一次了,所以就没有必要再往上跑一次。假如每次匹配完我令temp->count=0,然后while循环里少了temp->count!=-1的话也是可以过的,前者200ms,后者600ms,就是因为多了不必要的计算。下面贴一记代码

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
//
//  main.cpp
//  AC auto machine
//
//  Created by change on 14-1-24.
//  Copyright (c) 2014年 chanme. All rights reserved.
//
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <algorithm>
#define MAXCHAR 26
#define maxn 500000
using namespace std;
 
struct TrieNode
{
    int count;
    TrieNode* next[MAXCHAR];
    TrieNode* fail;
    void init()
    {
        memset(next,0,sizeof(next));
        fail=NULL;
        count=0;
    }
}T[maxn],*Trie;
int top;
 
void insert(char *c)
{
    int len=(int)strlen(c);TrieNode *p=Trie;
    for(int i=0;i<len;i++){
        if(p->next[c[i]-‘a‘]!=NULL){
            p=p->next[c[i]-‘a‘];
        }
        else{
            T[top].init();
            p->next[c[i]-‘a‘]=&T[top++];
            p=p->next[c[i]-‘a‘];
        }
    }
    p->count++;
}
 
void getFail()
{
    queue<TrieNode *> que;  // 用于BFS的队列
    que.push(Trie); // 将根结点压入
    Trie->fail=NULL; // 根结点的失配指针为NULL
    while(!que.empty())
    {
        TrieNode* temp=que.front();
        que.pop();
        TrieNode* p=NULL;
        // 枚举每个后继
        for(int i=0;i<MAXCHAR;i++){
            // 后继非空时计算其失配指针
            if(temp->next[i]!=NULL) {
                // 根结点的所有后继的失配指针指向根结点
                if(temp==Trie){
                    temp->next[i]->fail=Trie;
                }
                else{
                    // 否则的话,沿着失配指针走,遇到有相同后继的则连失配指针
                    p=temp->fail;
                    while(p!=NULL){
                        if(p->next[i]!=NULL){
                            temp->next[i]->fail=p->next[i];
                            break;
                        }
                        p=p->fail;
                    }
                    // 否则也指向根结点
                    if(p==NULL) temp->next[i]->fail=Trie;
                }
                // 压入队列
                que.push(temp->next[i]);
            }
        }
    }
}
 
int query(char *c)
{
    int len=(int)strlen(c);
    int res=0;
    TrieNode *p=Trie;
    for(int i=0;i<len;i++){
        while(p->next[c[i]-‘a‘]==NULL && p!=Trie) p=p->fail;
        p=p->next[c[i]-‘a‘];
        if(p==NULL) p=Trie;
        TrieNode *temp=p;
        while(temp!=Trie&&temp->count!=-1){
            res+=temp->count;
            temp->count=-1;
            temp=temp->fail;
        }
    }
    return res;
}
 
char str[55];
char text[1005000];
int n;
 
 
int main()
{
    int cas;cin>>cas;
    while(cas--)
    {
        top=0;T[top].init();
        Trie=&T[top++];
        cin>>n;
        for(int i=0;i<n;i++){
            scanf("%s",str);
            insert(str);
        }
        getFail();
        scanf("%s",text);
        printf("%d\n",query(text));
    }
    return 0;
}

HDU2222 Keywords Search AC自动机

上一篇:opencv中的洪水填充算法


下一篇:XML 编辑器 介绍