3 aaa bbb ccc 2 aaabbbccc bbaacc
web 1: 1 2 3 total: 1
来吧，题目读完了，先吐槽一发。窝草尼玛，这道题为什么会挂空间？
/*
Author: Lucifinil.
Date: 2016-7-23.
Description:
AC自动机算法求解多模式匹配问题.
problem_id: HDU 2896
*/
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
//声明 Trie 字典树 类
int n;
struct Trie
{
#define sigma_size 128
//sigma_size -> 字符集大小
public:
//构造函数[公有] 初始化
Trie()
{
cnt = 0;
Fail = NULL;
for(int i=0;i<sigma_size;i++)next[i]=NULL;
}
Trie* Fail;//Fail指针
Trie* next[sigma_size];//next[]指针
int cnt;//编号
};
//优化空间
//#define max_len 210
//char tmp[max_len];//临时储存特征码
//Insert() ->将特征码插入字典树Trie
void Insert(char* str,Trie* root,int id)
{
//因为指针退化，所以*str指向tmp[]中的第一个元素
//我们只需要将str++,便可以遍历tmp[]
//字符串以 '\0' 结束 条件为假结束循环
while(*str)
{
//在ASCII码中0~31及127(共33个)是控制字符或通信专用字符.所以
int index = *str - 31;//算出下标
if(root->next[index]==NULL)
root->next[index] = new class Trie;
root = root ->next[index];
//由于作用域的缘故此处的root指针并不是全局的指向Trie树根节点的指针
str++;
}
root->cnt = id;//记录这是第几个病毒的特征码
}
/*
getFail(Trie* root)
Description:计算Fail指针（失配指针），便于使用AC自动机求解。
计算时要用到队列queue进行bfs遍历.
*/
queue<Trie*> q;
void getFail(Trie* root)
{
root->Fail = NULL;
q.push(root);
while(!q.empty())
{
Trie* p = q.front();q.pop();
for(int i=0;i<sigma_size;i++)
{
if(p->next[i]!=NULL)
{
/*
两种处理 如果p是root（Trie树的root不代表任何字符）
所以当前遍历的节点的Fail指针指向root.
否则，遍历p的失配指针.将p的儿子节点的Fail指针指向
p失配指针所指向节点的儿子。
*/
if(p==root)p->next[i]->Fail = root;
else
{
Trie* ptr = p->Fail;
while(p!=NULL)
{
if(ptr->next[i]!=NULL)p->next[i]->Fail = ptr->next[i];
break;
}
if(ptr==NULL)//遍历一圈没找到，那么指向root.（重新开始）
{
p->next[i]->Fail = root;
}
}
q.push(p->next[i]);
}
}
}
}
int m;
#define max_len2 10010
char pat[max_len2];//网站源码长度
#define maxn 501
bool mark[maxn];
/*
int query(Trie* root,char* pat)
Description: 匹配str.
*/
int query(Trie* root,char* str)
{
Trie* p = root;
int tot = 0;//匹配成功的个数 [返回值]
while(*str)
{
int index = *str - 31;//计算下标
while(p->next[index]==NULL&&p!=root)p=p->Fail;//失配就沿着失配指针走
//特判当前是不是根，因为根失配就无法匹配..
p = p->next[index];//2种情况 无法匹配或者找到匹配点
if(p==NULL)p=root;//重新开始
Trie* ptr = p;
while(ptr!=root&&ptr->cnt!=0)
{
//匹配成功一个
if(!mark[ptr->cnt])
{
tot++;
mark[ptr->cnt] = 1;
}
ptr = ptr -> Fail;
}
str++;
}
return tot;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
Trie* root = new class Trie;//创建根节点
getchar();//读回车
for(int i=1;i<=n;i++)
{
scanf("%s",pat);
Insert(pat,root,i);
}
getFail(root);//在当前Trie树中获取Fail指针 [AC自动机]
scanf("%d",&m);
int tot = 0;
for(int i=1;i<=m;i++)
{
memset(mark,0,sizeof(mark));
scanf("%s",pat);
int flag = query(root,pat);//开始匹配
if(flag)//匹配成功
{
printf("web %d:",i);
for(int j=1;j<=n;j++)
if(mark[j])printf(" %d",j);
puts("");//输出换行
tot++;
}
}
printf("total: %d\n",tot);
}
return 0;
}这么优美的代码为什么会MLE or RE（运行期间爆空间）.
然而。。。
</pre><pre style="color: rgb(0, 0, 0); font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; widows: 1; word-spacing: 0px; -webkit-text-stroke-width: 0px;">/*
Author: Lucifinil.
Date: 2016-7-23.
Description:
AC自动机算法求解多模式匹配问题.
problem_id: HDU 2896
*/
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
//声明 Trie 字典树 类
int n;
struct Trie{
Trie *next[95];
Trie *fail;
int cnt;
Trie ()
{
fail=NULL;
cnt=0;
for (int i=0;i<95;i++)
{
next[i]=NULL;
}
}
}*e[100005];
#define max_len 210
char tmp[max_len];//临时储存特征码
//Insert() ->将特征码插入字典树Trie
void Insert(char* str,Trie* root,int id)
{
//因为指针退化，所以*str指向tmp[]中的第一个元素
//我们只需要将str++,便可以遍历tmp[]
//字符串以 '\0' 结束 条件为假结束循环
while(*str)
{
//在ASCII码中0~31及127(共33个)是控制字符或通信专用字符.所以
int index = *str - 31;//算出下标
if(root->next[index]==NULL)
root->next[index] = new class Trie;
root = root ->next[index];
//由于作用域的缘故此处的root指针并不是全局的指向Trie树根节点的指针
str++;
}
root->cnt = id;//记录这是第几个病毒的特征码
}
/*
getFail(Trie* root)
Description:计算Fail指针（失配指针），便于使用AC自动机求解。
计算时要用到队列queue进行bfs遍历.
*/
queue<Trie*> q;
void getFail(Trie* root)
{
int tou=0,tail=1;
e[0]=root;
root->fail=NULL;
while (tou<tail)
{
Trie *p=e[tou++];
Trie *temp=NULL;
for(int i=0;i<95;i++)
{
if(p->next[i])
{
if(p==root)
p->next[i]->fail=root;
else
{
Trie *pre=p->fail;
while(pre)
{
if(pre->next[i])
{
p->next[i]->fail=pre->next[i];
break;
}
pre=pre->fail;
}
if(!pre)
p->next[i]->fail=root;
}
e[tail++]=p->next[i];
}
}
}
}
int m;
#define max_len2 10010
char pat[max_len2];//网站源码长度
#define maxn 501
int mark[maxn];
/*
int query(Trie* root,char* pat)
Description: 匹配str.
*/
int query(Trie* root,char* str)
{
Trie* p = root;
int tot = 0;//匹配成功的个数 [返回值]
while(*str)
{
int index = *str - 31;//计算下标
while(p->next[index]==NULL&&p!=root)p=p->fail;//失配就沿着失配指针走
//特判当前是不是根，因为根失配就无法匹配..
p = p->next[index];//2种情况 无法匹配或者找到匹配点
if(p==NULL)p=root;//重新开始
Trie* ptr = p;
while(ptr!=root&&ptr->cnt!=0)
{
//匹配成功一个
if(!mark[ptr->cnt])
{
tot++;
mark[ptr->cnt] = 1;
}
ptr = ptr -> fail;
}
str++;
}
return tot;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
Trie* root = new class Trie;//创建根节点
getchar();//读回车
for(int i=1;i<=n;i++)
{
scanf("%s",tmp);
Insert(tmp,root,i);
}
getFail(root);//在当前Trie树中获取Fail指针 [AC自动机]
scanf("%d",&m);
int tot = 0;
for(int i=1;i<=m;i++)
{
memset(mark,0,sizeof(mark));
scanf("%s",pat);
int flag = query(root,pat);//开始匹配
if(flag)//匹配成功
{
printf("web %d:",i);
for(int j=1;j<=n;j++)
if(mark[j])printf(" %d",j);
puts("");//输出换行
tot++;
}
}
printf("total: %d\n",tot);
}
return 0;
}把next[]改小就过了。。。这TM我还有什么话说...
再给一份数组版本代码
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct Trie
{
int next[210*500][128],fail[210*500],end[210*500];
int root,L;
int newnode()
{
for(int i = 0;i < 128;i++)
next[L][i] = -1;
end[L++] = -1;
return L-1;
}
void init()
{
L = 0;
root = newnode();
}
void insert(char s[],int id)
{
int len = strlen(s);
int now = root;
for(int i = 0;i < len;i++)
{
if(next[now][s[i]] == -1)
next[now][s[i]] = newnode();
now=next[now][s[i]];
}
end[now]=id;
}
void build()
{
queue<int>Q;
fail[root] = root;
for(int i = 0;i < 128;i++)
if(next[root][i] == -1)
next[root][i] = root;
else
{
fail[next[root][i]] = root;
Q.push(next[root][i]);
}
while(!Q.empty())
{
int now = Q.front();
Q.pop();
for(int i = 0;i < 128;i++)
if(next[now][i] == -1)
next[now][i] = next[fail[now]][i];
else
{
fail[next[now][i]] = next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
bool used[510];
bool query(char buf[],int n,int id)
{
int len = strlen(buf);
int now = root;
memset(used,false,sizeof(used));
bool flag = false;
for(int i = 0;i < len;i++)
{
now = next[now][buf[i]];
int temp = now;
while(temp != root)
{
if(end[temp] != -1)
{
used[end[temp]] = true;
flag = true;
}
temp = fail[temp];
}
}
if(!flag)return false;
printf("web %d:",id);
for(int i = 1;i <= n;i++)
if(used[i])
printf(" %d",i);
printf("\n");
return true;
}
};
char buf[10010];
Trie ac;
int main()
{
int n,m;
while(scanf("%d",&n) != EOF)
{
ac.init();
for(int i = 1;i <= n;i++)
{
scanf("%s",buf);
ac.insert(buf,i);
}
ac.build();
int ans = 0;
scanf("%d",&m);
for(int i = 1;i <= m;i++)
{
scanf("%s",buf);
if(ac.query(buf,n,i))
ans++;
}
printf("total: %d\n",ans);
}
return 0;
}[hdu 2896] 病毒侵袭 [ac自动机][病毒特征码匹配]
原文：http://blog.csdn.net/qq_33583069/article/details/52014831