洛谷 P3966 [TJOI2013]单词（AC自动机， fail 树）

[TJOI2013]单词

题目描述

小张最近在忙毕设,所以一直在读论文。一篇论文是由许多单词组成但小张发现一个单词会在论文中出现很多次，他想知道每个单词分别在论文中出现了多少次。

输入格式

第一行一个整数 $N$，表示有 $N$ 个单词。

接下来 $N$ 行每行一个单词,每个单词都由小写字母 $a-z$ 组成。

输出格式

输出 $N$ 个整数,第 $i$ 行的数表示第 $i$ 个单词在文章中出现了多少次。

样例 #1

样例输入 #1

3
a
aa
aaa
1
2
3
4

样例输出 #1

6
3
1
1
2
3

提示

数据规模与约定

• $30\%$ 的数据， 单词总长度不超过 $10^3$。

• $100\%$ 的数据，$1\le n\le 200$，单词总长度不超过 $10^6$。

  1、题目和 P5357 【模板】AC 自动机（二次加强版） 一样，
  不同的是， 文本串有 n 个， 也就是查询 query n次。

#include 
using namespace std;
const int N = 210, M = 1e6 + 10;
int ch[M][26], ne[M], idx;
string s[N];
int n;

int ans[M]; // ans[i]表示第i个字符串出现的次数
int mp[N];	// mp[x] 表示第x个字符串，对应的 AC自动机上的节点


int tot;
int ver[M], head[M], Next[M];

void add(int x, int y)
{
	ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}

void dfs(int x)
{
	for(int i = head[x]; i; i = Next[i])
	{
		int y = ver[i];
		dfs(y);
		ans[x] += ans[y];
	}
}

void insert(int k)
{
	int p = 0, len = s[k].size();
	for(int i = 0; i < len; ++i)
	{
		int j = s[k][i] - 'a';
		if(!ch[p][j])
			ch[p][j] = ++idx;
		p = ch[p][j];
	}
	mp[k] = p;
}

void build()
{
	queue<int> q;
	for(int i = 0; i < 26; ++i)
	{
		if(ch[0][i])
			q.push(ch[0][i]);
	}
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		for(int i = 0; i < 26; ++i)
		{
			int v = ch[u][i];
			if(v)
			{
				ne[v] = ch[ne[u]][i], q.push(v);
			}else{
				ch[u][i] = ch[ne[u]][i];
			}
		}
	}
	for(int v = 1; v <= idx; ++v)
	{
		add(ne[v], v);
	}
}



void query(string s)
{
	int len = s.size();
	for(int k = 0, i = 0; k < len; ++k)
	{
		i = ch[i][s[k] - 'a'];
		ans[i]++;
	}
	return;
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
	{
		cin >> s[i];
		insert(i);
	}
	build();
	for(int i = 1; i <= n; ++i)
		query(s[i]);
	dfs(0);
	for(int i = 1; i <= n; ++i)
		printf("%d\n", ans[mp[i]]);
	return 0;
}
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