hdu 6096 String trie

缘起

hdu 6096 String

练习trie，此题的打法是标准trie

分析

题意

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
Bob有一个字典，里面有N个单词。
现在有一个单词列表，其中单词的中间部分有连续的字母消失。中间部分不包括第一个和最后一个字符。
我们只知道每个单词的前缀和后缀，并且缺少的字符数是不确定的，它可以是0.但是每个单词的前缀和后缀不能重叠。
对于列表中的每个单词，Bob想要通过前缀和后缀确定字典中的哪个单词。
可能有很多答案。 你只需要弄清楚有多少单词可能是答案。

【输入】
输入的第一行给出了测试用例T的数量; T测试案例如下。
每个测试用例包含两个整数N和Q，字典中的单词数以及列表中的单词数。
接下来的N行，每行有一个字符串Wi，表示字典中的第i个单词（0 <| Wi |≤100000）
下一个Q行，每行有两个字符串Pi，Si，表示列表中第i个单词的前缀和后缀（0 <| Pi |，| Si |≤100000,
0<| Pi | + | Si |≤100000）
以上所有字符均为小写字母。
字典不包含相同的单词。

【输出】
对于每个测试用例，输出Q行（每行一个整数）表示列表中每个单词的答案。

【样例输入】
1
4 4
aba
cde
acdefa
cdef
a a
cd ef
ac a
ce f

【样例输出】
2
1
1
0

【限制】
Time limit 3000 ms
Memory limit 524288 kB

打法就是标准trie. 但是转换为标准trie是有一些技巧的. 就是如何解决如下一件事情:

1
只遍历一次就能知道p和s这两个单词是单词w的前缀和后缀.

假设w的长度是n, p的长度是m, s的长度是k， 则

答案是将w[0,…,n-1]这样排序（称为字符序列A, 2n个字符）

w[0],w[n-1],w[1],w[n-2],…,w[n-1],w[0]

然后p和s按照如下顺序排序（称为字符序列B）

p[0],s[k-1],p[1],s[k-2],…

例如 “a” 和 “cbbb” 转换为 “ab#b#b#c”, “abc” 和 “d” 转换为 “adb#c#” 即不足的以 # 填充

如果B是A的前缀的话, 则就表明p和s分别是w的前缀和后缀. （是不是很巧妙?）

所以只需要将给定的N个单词如上处理之后，构建标准trie. 然后对于每对询问，只需要同样构建相应的字符串B，将其插入trie, 然后就和 【1】是一个路子了. 说破了思路——本题就一钱不值了。 但是实际上做起来，细节上想破了头. 因为按照上面的路子—— ab 的话, 给出 ab 和 ba 也将匹配——但是题目说前后缀长度加起来<=原字符串的长度. 所以我就想了各种不就措施——都快绝望了. 还是网上看了菊苣的文章——排序!!! 妈的，我怎么没想到排序?

将单词和询问都读入, 然后按照长度降序排序. 则先读入长度最长（即前缀+后缀长度最长）的询问, 则只会加入少量的字符串到trie中（这些字符串的长度>=本次前缀+后缀的长度）, 然后运行上面说的算法，并且不会出现刚刚说的问题. 即本题采用的是离线算法. 正如林九郎所言——细微之处，方见功夫.

但是网上也流行AC自动机的解法，关于AC自动机，我后面会继续写文章论述.

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <ctype.h>

using namespace std;
//#define LOCAL

char w[500005], ps[500005], t[200005]; // w用于保存一个样例中读入的全部单词, ps用于保存一个样例中读入的所有询问, t用于保存前缀和后缀预处理之后的结果(预处理的方式参见文章)
int n,q, ans[100005]; // ans 装着答案
struct xx // 每个单词在w中的位置信息的结构体
{
	int start,end;
	bool operator <(xx x) // 按照长度降序排序
	{
		return end-start > x.end-x.start;
	}
}zz[100005]; // 存储着所有单词在w中所在的位置（起始索引和终结索引）

struct qq // 询问的结构体
{
	int start, end, sep, index; // [start, sep]是前缀, [sep+1, end]是后缀, index是该询问原本的索引
	bool operator <(qq q)
	{
		return end-start > q.end-q.start;
	}
}qqs[100005];

typedef struct TrieNdoe 
{
	int ch, cnt;
	TrieNdoe *next[26];
	TrieNdoe(int ch=0):ch(ch),cnt(1){memset(next, 0,sizeof(next));}
} *Trie;

Trie root;

void del(Trie &p) // 清空树
{
	if (!p)
	{
		return;
	}
	for (int i = 0; i<26;i++)
	{
		del(p->next[i]);
	}
	delete p;
	p = 0;
}

void insert(int j) // 将zz[j]中的单词经过文章中说的处理之后插入trie
{
	Trie p = root;
	for (int i = zz[j].start,k = zz[j].end; i<=zz[j].end,k>=zz[j].start; i++,k--)
	{
		if (p->next[w[i]-'a'])
		{
			p->next[w[i]-'a']->cnt++;
		}
		else
		{
			p->next[w[i]-'a'] = new TrieNdoe(w[i]);
		}
		p = p->next[w[i]-'a'];

		if (p->next[w[k]-'a'])
		{
			p->next[w[k]-'a']->cnt++;
		}
		else
		{
			p->next[w[k]-'a'] = new TrieNdoe(w[k]);
		}
		p = p->next[w[k]-'a'];
	}
}

void prehandle(int i) // 将qqs[i]中的前缀和后缀预处理进入t
{
	int len = 0;
	int k = qqs[i].start, j = qqs[i].end;
	while(k<=qqs[i].sep && j>=qqs[i].sep+1)
	{
		t[len++] = ps[k];
		t[len++] = ps[j];
		k++;
		j--;
	}
	while(k<=qqs[i].sep)
	{
		t[len++] = ps[k++];
		t[len++] = '#';
	}
	while(j>=qqs[i].sep+1)
	{
		t[len++] = '#';
		t[len++] = ps[j--];
	}
	t[len] = 0;
}

int zs(int e, Trie p) // t+e 在 以p为根的trie中
{
	int k = 0;
	while(t[e+k]) // 将t+e插入trie
	{
		if (isalpha(t[e+k]) && p->next[t[e+k]-'a'])
		{
			p = p->next[t[e+k]-'a'];
		}
		else if (t[e+k]=='#') // 如果是通配符的话, 则其实当前节点p往哪里走都是可以的——就看哪里有了
		{
			int ret = 0;
			for (int i = 0; i<26;i++)
			{
				if (p->next[i]) // 如果有的话，就往这里走
				{
					ret += zs(e+k+1, p->next[i]);
				}
			}
			return ret;
		}
		else
		{
			return 0;
		}
		k++;
	}
	return p->cnt;
}

int query(int i) // 回答询问 qqs[i]
{
	prehandle(i); // 将前缀后缀预处理进入t
	return zs(0, root);
}

int main(void)
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		root = new TrieNdoe();
		scanf("%d%d", &n, &q);
		int z = 0;
		for (int i = 0,len; i<n;i++)
		{
			zz[i].start = z;
			scanf("%s", w+z);
			len = strlen(w+z);
			z+=len;
			zz[i].end = z-1;
		}
		sort(zz, zz+n); // 按长度降序排序
		z = 0;
		for (int i = 0,len; i<q;i++)
		{
			scanf("%s", ps+z);
			len = strlen(ps+z);
			qqs[i].start = z;
			z+=len;
			qqs[i].sep = z-1;
			scanf("%s", ps+z);
			len = strlen(ps+z);
			z+=len;
			qqs[i].end = z-1;
			qqs[i].index = i;
		}
		sort(qqs, qqs+q); // 上面的处理考验coder的输入输出处理基本功
		int j =0; // xx中上升的索引
		for (int i = 0; i<q;i++)
		{
			while(zz[j].end-zz[j].start>=qqs[i].end-qqs[i].start) // 只要长度比当前询问大
			{
				insert(j); // 才插入trie
				j++;
			}
			ans[qqs[i].index] = query(i); // 回答此次询问并缓存起来
		}
		for (int i = 0; i<q;i++) // 最后一口气回答所有询问——所谓离线算法就是这个意思
		{
			printf("%d\n", ans[i]);
		}
		del(root); // 清空树
	}
	return 0;
}

ac情况

Status Accepted
Time 1684ms
Memory 75784kB
Length 3207
Lang C++
Submitted 2019-07-28 17:44:25
Shared
RemoteRunId 29950272

额，时间比较长，可以说是水过~

参考

【1】https://yfsyfs.github.io/2019/07/21/hdu-1251-%E7%BB%9F%E8%AE%A1%E9%9A%BE%E9%A2%98-trie/