欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

AC自动机模板题-HDU-2222-Keywords Search

程序员文章站 2022-03-04 21:11:10
...

AC自动机模板题-HDU-2222-Keywords Search

地址: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;
}

 

相关标签: 算法