Post 4

Veröffentlicht am | Edited on

你要堕落，神仙也救不了； 你要成长，绝处也能逢生。

AC自动机（简单版）

题目背景

这是一道简单的AC自动机模板题。

用于检测正确性以及算法常数。

为了防止卡OJ，在保证正确的基础上只有两组数据，请不要恶意提交。

管理员提示：本题数据内有重复的单词，且重复单词应该计算多次，请各位注意

题目描述

给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。

输入输出格式

输入格式：

第一行一个n，表示模式串个数；

下面n行每行一个模式串；

下面一行一个文本串。

输出格式：

一个数表示答案

输入输出样例

输入样例#1：

1
2
3
4
2
a
aa
aa

输出样例#1：

1
2

说明

subtask1[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6,n=1；

subtask2[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6；

题解

AC自动机最简单的实现

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#define maxn 1050005
#define maxc 28
int cur = 1 ,  n;
char p[maxn] , s[maxn];
struct AC_Automaton
{
	int tr[maxn][maxc] , tot , next[maxn] , Ma[maxn] , f[maxn] , g[maxn];
	bool vis[maxn];
	AC_Automaton(){
		tot = 1;
	}
	inline void clear(){
		std::memset(f,0,sizeof(f));
		std::memset(g,0,sizeof(g));
		std::memset(next,0,sizeof(next));
	}
	inline void insert(char* s)
	{
		int len = std::strlen(s) , u = 1;
//		puts("The String:");
//		for(int i = 0 ; i < len ; ++i)
//			putchar(s[i]);
//		puts("OK");
		for(int i = 0 ; i < len ; ++i){
			int c = s[i] - 97;
			if(!tr[u][c])	tr[u][c] = ++ tot; 
			u = tr[u][c];
		}
		Ma[u] ++;
	}
	inline void GetFail()
	{
		std::queue<int> q;
		for(int i = 0 ; i < 26 ; ++i)
			tr[0][i] = 1;
		q.push(1) , next[1] = 0;
		while(!q.empty())
		{
			int k = q.front();
			q.pop();
			for(int i = 0 ; i < 26 ; ++i){
				if(!tr[k][i])	tr[k][i] = tr[next[k]][i];
				else{
					q.push(tr[k][i]);
					next[tr[k][i]] = tr[next[k]][i];
				}
			}
		}
	}
	inline int find(char* s)
	{
		int len = std::strlen(s + 1);
		int u = 1 , ans = 0 , k;
		for(int i = 1 ; i <= len ; ++i){
			k = tr[u][s[i]-97];
			while(k > 1){
				if(vis[k])	break;
				ans += Ma[k];
				Ma[k] = 0;
				vis[k] = true;
				k = next[k];
			}
			u = tr[u][s[i]-97];
		}
		return ans;
	}
	inline void print()
	{
		for(int i = 1 ; i <= tot ; ++i)
			printf("%d ",Ma[i]);
	}
}aton;
int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i){
		scanf("%s",p+cur);
		aton.insert(p+cur);
		cur += std::strlen(p+cur);
	}
	aton.GetFail();
	scanf("%s",s+1);
	printf("%d\n",aton.find(s));
}

AC自动机（加强版）

题目描述

有NN个由小写字母组成的模式串以及一个文本串TT。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串TT中出现的次数最多。

输入输出格式

输入格式：

输入含多组数据。

每组数据的第一行为一个正整数NN，表示共有NN个模式串，

接下去NN行，每行一个长度小于等于70的模式串。下一行是一个长度小于等于10^6106的文本串TT。

输入结束标志为N=0。

输出格式：

对于每组数据，第一行输出模式串最多出现的次数，接下去若干行每行输出一个出现次数最多的模式串，按输入顺序排列。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
10
11
12
13
2
aba
bab
ababababac
6
beta
alpha
haha
delta
dede
tata
dedeltalphahahahototatalpha
0

输出样例#1：

1
2
3
4
5
4
aba
2
alpha
haha

题解

本来想先写一个暴力，然后再写各种优化（比如记忆化甚至自动机dp）

结果发现暴力AC了，虽然有点慢。

根据题意，一个单词显然要被计算多次，所以不能访问过就不算了。

注意记录节点的父亲以及连向它的边，方便输出。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#include <stack>
#define maxn 1000005
#define maxc 26
int cur = 1 ,  n , ans[maxn];
char s[maxn] , p[maxn];
struct AC_Automaton
{
	int tr[maxn][maxc] , tot , next[maxn] , Ma[maxn] , f[maxn] , g[maxn];
	bool vis[maxn];
	AC_Automaton(){
		tot = 1;
	}
	inline void init()
	{
		tot = 1;
		std::memset(tr,0,sizeof(tr));
		std::memset(next,0,sizeof(next));
		std::memset(Ma,0,sizeof(Ma));
		std::memset(f,0,sizeof(f));
		std::memset(g,0,sizeof(g));
	}
	inline void insert(char* s)
	{
		int len = std::strlen(s) , u = 1;
		for(int i = 0 ; i < len ; ++i){
			int c = s[i] - 97;
			if(!tr[u][c])	tr[u][c] = ++ tot; 
			f[tr[u][c]] = u , g[tr[u][c]] = c , u = tr[u][c];
		}
		Ma[u] ++;
	}
	inline void GetFail()
	{
		std::queue<int> q;
		for(int i = 0 ; i < 26 ; ++i)
			tr[0][i] = 1;
		q.push(1) , next[1] = 0;
		while(!q.empty())
		{
			int k = q.front();
			q.pop();
			for(int i = 0 ; i < 26 ; ++i){
				if(!tr[k][i])	tr[k][i] = tr[next[k]][i];
				else{
					q.push(tr[k][i]);
					next[tr[k][i]] = tr[next[k]][i];
				}
			}
		}
	}
	inline int find(char* s)
	{
		int len = std::strlen(s + 1);
		int u = 1 , k;
		for(int i = 1 ; i <= len ; ++i){
			k = tr[u][s[i]-97];
			while(k > 1){
			//	if(vis[k])	break;
				ans[k] += Ma[k];
				//vis[k] = true;
				k = next[k];
			}
			u = tr[u][s[i]-97];
		}
		return ans[k];
	}
	inline void print(int k)
	{
		std::stack<int> st;
		while(k > 1)
		{
			st.push(g[k]);
			k = f[k];
		}
		while(!st.empty())
			printf("%c",st.top()+97) , st.pop();
	}
		
}aton;
int main()
{
	while(scanf("%d",&n) != EOF)
	{
		std::memset(ans,0,sizeof(ans));
		aton.init();
		cur = 1;
		if(n == 0) break;
		for(int i = 1 ; i <= n ; ++i)
		{
			scanf("%s",p+cur);
			aton.insert(p+cur);
			cur += std::strlen(p+cur);
		}
		aton.GetFail();
		scanf("%s",s+1);
		aton.find(s);
		int maxx = -0x7ffffff;
		std::queue<int> str;
		for(int i = 1 ; i <= aton.tot ; ++i)
			if(aton.Ma[i])
			{
				if(maxx < ans[i]){
					while(!str.empty())	str.pop();
					str.push(i);
					maxx = ans[i];
				}
				else if(maxx == ans[i]) str.push(i);
			}
		printf("%d\n",maxx);
		while(!str.empty())
			aton.print(str.front()) , putchar(10) , str.pop();
		
	}
}

「一本通 2.4 例 1」Keywords Search

题目描述

原题来自：HDU 2222

给定 nn 个长度不超过 5050 的由小写英文字母组成的单词准备查询，以及一篇长为 mm 的文章，问：文中出现了多少个待查询的单词。多组数据。

输入格式

第一行一个整数 TT，表示数据组数；
对于每组数据，第一行一个整数 nn，接下去 nn 行表示 nn 个单词，最后一行输入一个字符串，表示文章。

输出格式

对于每组数据，输出一个数，表示文中出现了多少个待查询的单词。

样例

样例输入

1
2
3
4
5
6
7
8
1
5
she
he
say
shr
her
yasherhs

样例输出

1
3

数据范围与提示

对于全部数据，

题解

AC自动机的板子。

结果我还各种错。感觉虽然完全理解AC自动机的复杂度，正确性和工作原理，但是Trie图优化还是经常写错哎。。

Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#define maxn 1000005
#define maxc 26
char s[maxn];
int n;
struct AC_Automaton
{
	int tr[maxn][maxc] , next[maxn] , tot , la[maxn];
	bool vis[maxn];
	AC_Automaton(){
		tot = 1;
	}
	inline void insert(char* s)
	{
		int len = std::strlen(s) , u = 1;
		for(int i = 0 ; i < len ; ++i)
		{
			if(!tr[u][s[i]-97])	tr[u][s[i]-97] = ++tot;
			u = tr[u][s[i]-97];
		}
		la[u] ++ ;
	}
	inline void clear()
	{
		std::memset(tr,0,sizeof(tr));
		std::memset(la , 0 , sizeof(la));
		std::memset(next,0,sizeof(next));
		std::memset(vis,false,sizeof(vis));
		tot = 1;
	}
	inline void GetFail()
	{
		std::queue<int> q;
		for(int i = 0 ; i < 26 ; ++i)
			tr[0][i] = 1;
		q.push(1) , next[1] = 0;
		while(!q.empty())
		{
			int k = q.front();
			q.pop();
			for(int i = 0 ; i < 26 ; ++i)
			{
				if(!tr[k][i])	tr[k][i] = tr[next[k]][i];
				else
				{
					q.push(tr[k][i]);
					int v = next[k];
					next[tr[k][i]] = tr[v][i];
				}
			}
		}
	}
	inline int find(char* s)
	{
		int u = 1 , ans = 0 , len = std::strlen(s);
		for(int i = 0 ; i < len ; ++i)
		{
			int c = s[i] - 97;
			int k = tr[u][c];
			while(k > 1)
			{
				if(vis[k]) break;
				ans += la[k];
				vis[k] = true;
				la[k] = 0;
				k = next[k];
			}
			u = tr[u][c];
		}
		return ans;
	}
}aton;
int main()
{
	int t;
	scanf("%d",&t);
	while(~(--t))
	{
		scanf("%d",&n);
		aton.clear();
		int cur = 1;
		for(int i = 1 ; i <= n ; ++i)
		{
			scanf("%s",s+cur);
			aton.insert(s+cur);
			cur += std::strlen(s+cur);
		}
		aton.GetFail();
		scanf("%s",s+1);
		printf("%d\n",aton.find(s+1));
	}
}