- 论坛徽章:
- 0
|
回复 17# 独孤九贱
=======================================================
简单解释：
trie图：trie树改造成的有向图。目的是为了活用trie树这个简单而又NB的数据结构。
AC自动机：即trie图的一种活用，利用kmp思想添加了fail指针。能进行高效多模匹配。
=======================================================
========================================
AC自动机算法(Aho-Corasick Algorithm)
以hdu 2222 Keywords Search 为例：
功能：多模式匹配（动态结构）
使用说明：
1.trie_insert 构建以root为根的tire树(即keyword tree)，执行一次加入一个模式串。
2.construct_ac_automaton(root) 构建以root为根的trie树的fail指针。
3.query(str, root) 查询以root为根的trie树(模式串集合)中，有多少个模式串在文本串str中。
代码如下：
const int MAXN = 1000001; //文本串的最大长度MAXN - 1
const int MAXM = 51; //单词(模式串)的最大长度为MAXM - 1
const int KEYSIZE = 26; //26个小写字母
struct Node
{
Node *fail; //失败指针
Node *next[KEYSIZE]; //儿子结点个数
int count; //单词个数
Node()
{
fail = NULL;
count = 0;
memset(next, 0, sizeof(next));
}
/*
~Node() {
delete next;
} 貌似没用，在hoj加了这个内存不见减少*/
}*q[MAXN / 2];//??????MAXM*单词个数
char keyword[MAXM]; //单词(模式串 Pattern String)
char str[MAXN]; //文本串
//trie==keyword tree==a set of patterns
void trie_insert(char *str, Node *root)
{
Node *p = root;
int i = 0;
while(str) {
int index = str - 'a';
if(p -> next[index] == NULL)
p -> next[index] = new Node();
p = p -> next[index];
i ++;
}
p -> count ++; //在单词的最后一个结点count + 1,代表一个单词，允许有重复的单词
}
void construct_ac_automaton(Node *root)
{
int head, tail;
head = tail = 0;
q[tail ++] = root;
root -> fail = NULL;
while(head < tail)
{
Node *now = q[head ++];
for(int i = 0; i < KEYSIZE; i ++) if(now -> next != NULL)
{
q[tail ++] = now -> next;//加入head能走的节点
if(now == root){//如果当前节点是root，则fail指针指向自己。
now -> next -> fail = root;
continue;
}
Node *p = now -> fail;
while(p != NULL) {
if(p -> next != NULL) {
now -> next -> fail = p -> next;
break;
}
p = p -> fail;
//不断转移到下一个fail节点，直到形成如'h'->'h'->....->'h'->root的链
//且每个'h'之后的字母都不同于 i+'a'
}
if(p == NULL) now -> next -> fail = root;
}
}
}
int query(char *str, Node *root)
{
int i = 0, cnt = 0;
Node *p = root;//表示当前节点
while(str) {
int index = str - 'a';
while(p -> next[index] == NULL && p != root) p = p -> fail;
//直到p存在字母为str的儿子
p = p -> next[index];
p = (p == NULL) ? root : p;
Node *temp = p;
//不管当前节点p是否为一个单词的某位尾，把fail链上的节点都标记为已访问
//统计链上count=1的节点数，且访问完一个节点就把该节点的count置-1
while(temp != root && temp -> count != -1) {
cnt += temp -> count;
temp -> count = -1;
temp = temp -> fail;
}
i ++;
}
return cnt;
}
void run_AC()
{
int n, cas;
Node *root;
scanf("%d", &cas);
while(cas --)
{
scanf("%d", &n);
root = new Node();
while(n --) {
scanf("%s", keyword);
trie_insert(keyword, root);
}
construct_ac_automaton(root);
scanf("%s", str);
printf("%d\n", query(str, root));
}
} |
|
免费注册
楼主: lujian19861986
发表于 2011-10-24 09:17
发表于 2011-10-24 10:01
