AC自动机模板题-HDU-2222-Keywords Search
程序员文章站
2022-03-04 21:11:10
...
地址:http://acm.hdu.edu.cn/showproblem.php?pid=2222
Code:AC自动机模板:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct node{
int fail;
int next[26];
int sum;
};
const int MAX_S=500005;
const int MAX_N=1000005;
char ss[MAX_N],str[55];
int n,T,num;
node Trie[MAX_S];
void Insert(char s[]);
void Build();
int Find(char s[]);
int Get(int u);
int main()
{
scanf("%d",&T);
while(T--){
memset(Trie,0,sizeof(Trie));
num=0;
scanf("%d",&n);
for(int i=0;i<n;++i)
{
scanf("%s",str);
Insert(str);
}
Build();
scanf("%s",ss);
printf("%d\n",Find(ss));
}
return 0;
}
void Insert(char s[])
{
int u=0,len=strlen(s);
for(int i=0;i<len;++i)
{
int t=s[i]-'a';
if(Trie[u].next[t]==0) Trie[u].next[t]=++num;
u=Trie[u].next[t];
}
++Trie[u].sum;
}
void Build()
{
queue<int> Q;
Q.push(0);
while(!Q.empty()){
int u=Q.front(); Q.pop();
for(int i=0;i<26;++i)
{
int p=Trie[u].next[i];
if(p){
int v=u;
while(v){
v=Trie[v].fail;
if(Trie[v].next[i]){
Trie[p].fail=Trie[v].next[i]; break;
}
}
Q.push(p);
}
}
}
}
int Find(char s[])
{
int u=0,t,res=0;
int len=strlen(s);
for(int i=0;i<len;++i)
{
t=s[i]-'a';
if(Trie[u].next[t]) u=Trie[u].next[t];
else{
int p=u;
while(p){
p=Trie[p].fail;
if(Trie[p].next[t]){
u=Trie[p].next[t]; break;
}
}
if(!Trie[p].next[t]) u=0;
}
if(Trie[u].sum)
res+=Get(u);
}
return res;
}
int Get(int u)
{
int res=0;
while(u){
res+=Trie[u].sum;
Trie[u].sum=0;
u=Trie[u].fail;
}
return res;
}
Code 2:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAX_N=10005;
struct Tree{//字典树
int fail;//失配指针
int vis[26];//子节点的位置
int end;//标记有几个单词以这个节点结尾
}AC[50*MAX_N];//Trie树
int cnt;//Trie的指针
inline void Insert(char s[])
{
int l=strlen(s),now=0;//字典树的当前指针
for(int i=0;i<l;++i)//构造Trie树
{
if(AC[now].vis[s[i]-'a']==0)//Trie树没有这个子节点
AC[now].vis[s[i]-'a']=++cnt;//构造出来
now=AC[now].vis[s[i]-'a'];//向下构造
}
AC[now].end+=1;//标记单词结尾
}
void Get_fail()//构造fail指针
{
queue<int> Q;//队列
for(int i=0;i<26;++i)//第二层的fail指针提前处理一下
if(AC[0].vis[i]!=0){
AC[AC[0].vis[i]].fail=0;//指向根节点
Q.push(AC[0].vis[i]);//压入队列
}
while(!Q.empty()){ //BFS求fail指针
int u=Q.front(); Q.pop();
for(int i=0;i<26;++i)//枚举所有子节点
if(AC[u].vis[i]!=0){ //存在这个子节点
AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];
Q.push(AC[u].vis[i]); //压入队列
}else AC[u].vis[i]=AC[AC[u].fail].vis[i];
}
}
int AC_Query(char s[])//AC自动机匹配
{
int l=strlen(s),now=0,ans=0;
for(int i=0;i<l;++i)
{
now=AC[now].vis[s[i]-'a'];//向下一层
for(int t=now;t&&AC[t].end!=-1;AC[t].end=-1,t=AC[t].fail)//循环求解
ans+=AC[t].end;
}
return ans;
}
int main()
{
int n,T;
scanf("%d",&T);
while(T--){
memset(AC,0,sizeof(AC));
cnt=0;
scanf("%d",&n);
char s[55],str[1000005];
for(int i=1;i<=n;++i)
{
scanf("%s",s);
Insert(s);
}
Get_fail();//求出失配指针
scanf("%s",str);//文本串
printf("%d\n",AC_Query(str));
}
return 0;
}
上一篇: 安装Docker Compose