AC自动机 (Trie 板子)

大自然的帮运工

使用板子注意事项:

注意:
1.串是否全是小写字母
2.根节点为1
3.节点数不超过maxn
4.多组数据注意 清空
5.复杂度嘛。。。。。建树o(n*len)

前置知识:Trie树

AC自动机 (Trie 板子)

需求:
给定n个模式串和1个文本串,求有多少个模式串在文本串里出现过。
输入n个模式串, 一个原串
输出结果: 原串中含有模式串的个数。

in:
6
abcd
cd
cd
cdac
aab 
abcdac
out:
5
#include<bits/stdc++.h>
#define maxn 1000001
using namespace std;
struct kkk{
	int son[26];  //一般是小写字母 所以26个 
	int flag; ///相同模式串出现次数 或者是标记 
    int fail;  /// 失配指针
    
}trie[maxn];   // maxn 树节点数 
int n, cnt;   // n个模式串  初始根编号 1 
string s;     // 子串 
//建字典树 
void insert(string s){
	int u = 1;
	int len = s.length();
	for (int i = 0; i < len;i++){
		int v = s[i] - 'a';
		if(!trie[u].son[v]){
			trie[u].son[v] = ++cnt;
		}
		u = trie[u].son[v];
	}
	trie[u].flag++;
}
// 设置失配指针   
// fail  当前字符串最长的后缀字符串 在Trie上的可以找到的编号 
void getFail(){
	
	for (int i = 0; i < 26;i++){
		trie[0].son[i] = 1;   
	}
	queue<int> q;
	q.push(1);
	// 失配 
	trie[1].fail = 0;
	while(!q.empty()){
		int fa = q.front();
		//cout<<fa<<endl;
		q.pop();
		int fafail = trie[fa].fail;
		for (int i = 0; i < 26;i++){
			int v = trie[fa].son[i];
			// 下面trie[v].fail = trie[fafail].son[i];
			// 有点dp的味道  
            if(!v){
            	//fa没有该v节点 所以用他的最长后缀字符串
				// 的儿子节点来代替他。 
				trie[fa].son[i] = trie[fafail].son[i];
				continue;
			}
			
			trie[v].fail = trie[fafail].son[i];
			q.push(v);
		}
	}
}
// 原串与模式串的 关系 
int query(string s){
	int u = 1, ans = 0;
	int len = s.length();
	// 这个循环也很好理解
	// 其实就是两个位置 i是串的右边,现在找该串的左边的位置j
	//  要求j到i是该模式串,那要怎么做呢,用前面的trie树和失配指针
	// 当然对于每个i有很多个j嘛, 模式串又不止一个是吧
	//  
	for (int i = 0; i < len;i++){
		int v = s[i] - 'a';
		int k = trie[u].son[v];
		 // while 模式串不止一个 所以有种关系是可以找出j
		 //  关系即是 k=trie[u].fail;  不断迭代 直至没得了 
		while(k>1 and trie[k].flag!=-1){
			ans += trie[k].flag;
			trie[k].flag = -1;
			k = trie[k].fail;
		}
		u = trie[u].son[v];
	}
	return ans;
}
int main(){
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	cnt = 1; 
	// Trie树  根节点是 1 ,什么都没有
	// 类型头指针 
	cin >> n;
	for (int i = 1; i <= n;i++){
		cin >> s;
		insert(s);
	}
	getFail();
	cin >> s;
	cout << query(s);
	return 0;
}

TWO (板子)

in:
2
aba
bab
ababababac
6
beta
alpha
haha
delta
dede
tata
dedeltalphahahahototatalpha
0
out:
4
aba
2
alpha
haha

需求:
1、求出现次数最多的次数
2、求出现次数最多的模式串
传送门
多组输入: 当n==0时退出。 注意每次用时clear清空

AC代码:

#include<bits/stdc++.h>
#define maxn 1000001
using namespace std;
struct kkk{
	int son[26];
	int flag; ///相同模式串出现次数 
    int fail;  /// 失配指针
    void clear(){
		memset(son, 0, sizeof(son));
		fail = flag = 0;
	}
}trie[maxn];
int n, cnt,ans;
string s;
string a[200];
int vis[200];
void insert(string s,int num){
	int u = 1;
	int len = s.length();
	for (int i = 0; i < len;i++){
		int v = s[i] - 'a';
		if(!trie[u].son[v]){
			trie[u].son[v] = ++cnt;
		}
		u = trie[u].son[v];
	}
	// 存位置 
	trie[u].flag=num;
}
void getFail(){
	for (int i = 0; i < 26;i++){
		trie[0].son[i] = 1;
	}
	queue<int> q;
	q.push(1);
	trie[1].fail = 0;
	while(!q.empty()){
		int fa = q.front();
		//cout<<fa<<endl;
		q.pop();
		int fafail = trie[fa].fail;
		for (int i = 0; i < 26;i++){
			int v = trie[fa].son[i];
            if(!v){
				trie[fa].son[i] = trie[fafail].son[i];
				continue;
			}
			trie[v].fail = trie[fafail].son[i];
			q.push(v);
		}
	}
}
int query(string s){
	int u = 1, ans = 0;
	int len = s.length();
	for (int i = 0; i < len;i++){
		int v = s[i] - 'a';
		int k = trie[u].son[v];
		while(k>1){
			// 找到了模式串就对该串的vis++ 
			if(trie[k].flag){
				vis[trie[k].flag]++;
			}
			k = trie[k].fail;
		}
		u = trie[u].son[v];
	}
	return ans;
}
void clear(){
	for (int i = 0; i <= cnt;i++){
		trie[i].clear();
	}
	for (int i = 1; i <= n;i++){
		vis[i] = 0;
	}
		cnt = 1;
	ans = 0;
}
void solve(){
	cnt = 1;
    while(1){
		scanf("%d",&n);
		if(n==0)
			break;
		clear();
		for (int i = 1; i <= n;i++)
		{
			cin >> a[i];
			insert(a[i], i);
		}
		getFail();
		cin >> s;
		query(s);
		for (int i = 1; i <= n;i++){
			ans = max(vis[i], ans);
		}
		cout << ans<<endl;
		for (int i = 1; i <= n;i++){
               if(vis[i]==ans){
				   cout << a[i] << endl;
			   }
		}
	}
	return  ;
}
int main(){
	freopen("in.txt", "r", stdin);
  	freopen("out.txt","w", stdout);
	solve();
	return 0;
}

上一篇:树形数据结构总结一(堆,Trie,并查集)


下一篇:Trie 字典树