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

hdu2222 Keywords Search(ac自动机模板-kuangbin)

程序员文章站 2022-07-03 09:10:35
Keywords Search题目大意:给定T组数据,首先是n个字符串,然后给定一段字符串,问这一段中出现过多少个前面的字符串。思路:很显然这是一个ac自动机的模板题,即给定n个子串然后拿一个比较长的主串进行匹配,当然要注意的是前面的n个字串可能有重复的,要单独处理。Code:kuangbin大神的代码模板真好用#include #include #include #include

Keywords Search

题目大意:

给定T组数据,首先是n个字符串,然后给定一段字符串,问这一段中出现过多少个前面的字符串。

思路:

很显然这是一个ac自动机的模板题,即给定n个子串然后拿一个比较长的主串进行匹配,当然要注意的是前面的n个字串可能有重复的,要单独处理。

Code:
kuangbin大神的代码模板真好用

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll long long
#define INT 9654234
using namespace std;
const int maxn = 500010;
struct Trie{
	int next[maxn][26],fail[maxn],end[maxn];
	int root,l;
	int newnode(){
		for(int i=0;i<26;i++) next[l][i]=-1;
		end[l++]=0;
		return l-1;
	}
	void init(){
		l=0;
		root =newnode();
	}
	void insert(char buf[]){
		int len=strlen(buf);
		int now=root;
		for(int i=0;i<len;i++){
			if(next[now][buf[i]-'a']==-1) 
				next[now][buf[i]-'a']=newnode();
			now=next[now][buf[i]-'a'];
		}
		end[now]++;
	}
	
	void bulid(){
		queue<int> q;
		fail[root]=root;
		for(int i=0;i<26;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<26;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]);
				}
			}
		}
	}
	int query(char buf[]){
		int len=strlen(buf);
		int now=root;
		int res=0;
		for(int i=0;i<len;i++){
			now=next[now][buf[i]-'a'];
			int temp=now;
			while(temp!=root){
				res+=end[temp];
				end[temp]=0;
				temp=fail[temp];
			}
		}
		return res;
	}
	void debug(){
		for(int i=0;i<l;i++){
			printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);
			for(int j=0;j<26;j++)
				printf("%2d",next[i][j]);
			printf("]\n");
		}
	}
} ac;

char buf[maxn<<1];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    int T,n;
    cin>>T;
    while(T--){
    	cin>>n;
    	ac.init();
    	for(int i=1;i<=n;i++){
    		cin>>buf;
    		ac.insert(buf);
		}
		ac.bulid();
		cin>>buf;
		cout<<ac.query(buf)<<endl;
	}
	return 0;
}

本文地址:https://blog.csdn.net/weixin_43872264/article/details/107418015

相关标签: ac自动机