首页 > 代码库 > POJ 1816 Trie

POJ 1816 Trie

2024-09-18 14:29:40   215人阅读

链接：

http://poj.org/problem?id=1816

题意：

先给你n个字符串，这些字符串包含小写字母，‘？’和‘*’，其中

‘？’可以表示任意一个字符，‘*’可以表示任意长度的任意字符，包括0个

然后m次询问，每次给你一个字符串，问你它和哪些字符串匹配

题解：

5月第一发AC真不容易啊（其实上个月就该A的

技术分享

这道题思路很简单，就是先建一个字典树，然后在字典树上跑dfs就好了，但是有几个需要注意的地方

当然如果方法不一样，可能就不会遇到这么多恶心的问题

首先最坑的就是题目中给的字符串会有一样的，所以就必须要用vector来存了

开始的时候dfs写错了，多写了一层循环，tle了

然后改完之后，wa了，发现是没有判断最后还有一个*的情况，然后加上之后又wa了

然后发现结尾可能不只有一个*，我的判断方式有问题，改好之后又wa了

忍不了就看了discuss，原来可能有重复的字符串，改成vector后结果又mle了。。。

果断把一个int数组改成short，然后又超时了。

大概是没加ios::sync_with_stdio(false), cin.tie(0);吧，加上之后继续wa。。

然后一想有重复的结点的话，直接输出是不行的（因为怕mle所以没有把答案先存下来）

虽然题目上没有说要排序输出，但既然不是special judge，还是要排序的，所以就只好先存了下来

然后排序，去重（我也不知道我为啥要去重，顺手去了0.0） 然后终于过了！！！

代码：

int pi = 1;struct Node {	short next[30];	VI id;	bool end;}tree[MAXN * 6];void insert(string s, int id) {	int index, p, i;	for (i = p = 0; s[i]; i++) {		if (isalpha(s[i])) index = s[i] - ‘a‘;		else if (s[i] == ‘?‘) index = 26;		else index = 27;		if (tree[p].next[index] == 0)			tree[p].next[index] = pi++;		p = tree[p].next[index];	}	tree[p].id.pb(id);	tree[p].end = 1;}VI ans;void dfs(string s, int cnt, int p) {	if (cnt == s.length()) {		if (tree[p].end)			rep(i, 0, tree[p].id.size())			ans.insert(ans.end(), all(tree[p].id));		if (!tree[p].next[27]) return;	}	int index = s[cnt] - ‘a‘;	if (tree[p].next[index])		dfs(s, cnt + 1, tree[p].next[index]);	if (tree[p].next[26])		dfs(s, cnt + 1, tree[p].next[26]);	if (tree[p].next[27]) rep(j, cnt, s.size() + 1)		dfs(s, j, tree[p].next[27]);}int main() {	ios::sync_with_stdio(false), cin.tie(0);	int n, m;	cin >> n >> m;	rep(i, 0, n) {		string s;		cin >> s;		insert(s, i);	}	while (m--) {		ans.clear();		string s;		cin >> s;		dfs(s, 0, 0);		sort(all(ans));		ans.erase(unique(all(ans)), ans.end());		if (ans.empty()) cout << "Not match";		else rep(i, 0, ans.size()) cout << ans[i] << ‘ ‘;		cout << endl;	}	return 0;}　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

POJ 1816 Trie


联系
我们