hdoj 2896 病毒侵袭(AC自动机)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2896

思路分析:题目为模式匹配问题,对于一个给定的字符串,判断能匹配多少个模式;该问题需要静态建树,另外需要对AC自动机的模板加以修改,

对于每个匹配的模式的最后一个单词的fail指针指向root,即可实现一个字符串进行多次模式匹配;

代码如下:

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int KIND = ;
const int MAX_NODE = * ;
const int MAX_M = + ;
char str[MAX_M];
int vir_match[MAX_M]; struct Trie {
int root, count;
int next[MAX_NODE][KIND], fail[MAX_NODE], end[MAX_NODE];
void Init()
{
count = ;
root = NewNode();
}
int NewNode()
{
for (int i = ; i < KIND; ++i)
next[count][i] = -;
end[count] = -;
return count++;
} void Insert(char *str, int id)
{
int i = , k = ;
int now = root; while (str[i])
{
k = str[i];
if (next[now][k] == -)
next[now][k] = NewNode();
now = next[now][k];
++i;
}
end[now] = id;
} void BuildAutomaton()
{
queue<int> Q; fail[root] = -;
Q.push(root);
while (!Q.empty())
{
int now = Q.front();
int p = -;
Q.pop(); if (end[now] != -)
fail[now] = root;
for (int i = ; i < KIND; ++i)
{
if (next[now][i] != -)
{
if (now == root)
fail[next[now][i]] = root;
else
{
p = fail[now];
while (p != -)
{
if (next[p][i] != -)
{
fail[next[now][i]] = next[p][i];
break;
}
p = fail[p];
}
if (p == -)
fail[next[now][i]] = root;
}
Q.push(next[now][i]);
}
}
}
} int Match(char *str)
{
int i = , k = , vir_count = ;
int p = root; while (str[i])
{
k = str[i];
while (next[p][k] == - && p != root)
p = fail[p];
p = next[p][k];
p = (p == -) ? root : p; if (end[p] != -)
{
vir_match[vir_count++] = end[p];
p = fail[p];
}
++i;
}
return vir_count;
}
}; Trie root; int main()
{
int vir_num = , web_num = ;
int match_count = , web_matched = ; while (scanf("%d\n", &vir_num) != EOF)
{
root.Init();
for (int i = ; i < vir_num; ++i)
{
gets(str);
root.Insert(str, i + );
} web_matched = ;
match_count = ;
root.BuildAutomaton();
scanf("%d\n", &web_num);
for (int i = ; i < web_num; ++i)
{
int ans = ; gets(str);
ans = root.Match(str);
sort(vir_match, vir_match + ans);
if (ans)
{
web_matched++;
printf("web %d: ", i + );
for (int j = ; j < ans - ; ++j)
printf("%d ", vir_match[j]);
printf("%d\n", vir_match[ans - ]);
}
}
printf("total: %d\n", web_matched);
}
return ;
}
上一篇:利用路由器搭建受限wifi热点,气死蹭网的坏人~


下一篇:JAVA基础学习day21--IO流三-File、Properties、PrintWriter与合并、分割流