本文主要是介绍POJ 1816 Wild Words（trie 树上的DFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
| Wild Words
Description A word is a string of lowercases. A word pattern is a string of lowercases, '?'s and '*'s. In a pattern, a '?' matches any single lowercase, and a '*' matches none or more lowercases. There are many word patterns and some words in your hand. For each word, your task is to tell which patterns match it. Input The first line of input contains two integers N (0 < N <= 100000) and M (0 < M <=100), representing the number of word patterns and the number of words. Each of the following N lines contains a word pattern, assuming all the patterns are numbered from 0 to N-1. After those, each of the last M lines contains a word. You can assume that the length of patterns will not exceed 6, and the length of words will not exceed 20. Output For each word, print a line contains the numbers of matched patterns by increasing order. Each number is followed by a single blank. If there is no pattern that can match the word, print "Not match". Sample Input 5 4 t* ?h*s ??e* *s ?*e this the an is Sample Output 0 1 3 0 2 4 Not match 3 Source POJ Monthly |
个人觉得这个题目是个好题目，但是测试数据有点让人吐血，有的AC代码有的测试数据根本通过不了，也能AC
这个题目我纠结了三个多小时，其实程序半小时就搞定了，谁能想到测试数据的样例有重复，而且重复的也要分顺序
输出！开始在trie树上每次保存一个，后来用vector保存多个结果，这才A
解题思路：
在pattern上建立trie树，每个节点保存出现的编号（编号可能不唯一），然后建立完成之后在trie树上进行搜索
那么就OK了
搜索的时候分三种情况，如果当前位置 ？ 可以那么直接跳过当前节点
如果 *可以，那么一直跳 0 1 2 3 结束
剩下的正常搜索
还要注意一种情况就是当字符串匹配结束后不能停止，还要判断后面有没有全是**的pattern
这个题目是个非常好的题目，测试数据也没什么大问题，就是你有重复倒是给个提示撒！
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
struct trie
{
trie *next[28];
vector<int> num;
}re_root,po[100000];
int pos,global_num;
int ans[100010];
int ans_pos;
int init(trie *root)
{
memset(root->next,0,sizeof(root->next));
root->num.clear();
return 0;
}
int insert_trie(trie *root,char *name)
{
if(name[0]==0)
{root->num.push_back(global_num);global_num++;//return 0;
}
if(name[0] >='a' && name[0] <='z')
{
if(root->next[name[0]-'a'])
insert_trie(root->next[name[0]-'a'],name+1);
else
{
root->next[name[0]-'a']=&po[pos];
init(&po[pos]);
pos++;
insert_trie(root->next[name[0]-'a'],name+1);
}
}
else
{
if(name[0]=='?')
{
if(root->next[26])
insert_trie(root->next[26],name+1);
else
{
root->next[26]=&po[pos];
init(&po[pos]);
pos++;
insert_trie(root->next[26],name+1);
}
}
else
{
if(root->next[27])
insert_trie(root->next[27],name+1);
else
{
root->next[27]=&po[pos];
init(&po[pos]);
pos++;
insert_trie(root->next[27],name+1);
}
}
}
return 0;
}
int query(trie *root,char *name)
{
int i,j,k;
if(name[0]==0 && !root->num.empty())
{
for(i=0;i<root->num.size();i++)
ans[ans_pos++]=root->num[i];
}
if(name[0]==0)
{
//root=root->next[27];
while(root)
{
if(!root->num.empty())
{
for(i=0;i<root->num.size();i++)
ans[ans_pos++]=root->num[i];
}
root=root->next[27];
}
return 0;
}
if(root->next[27])
{
for(i=0;name[i];i++)
{
query(root->next[27],name+i);
}
query(root->next[27],name+i);
}
if(root->next[26])
query(root->next[26],name+1);
if(root->next[name[0]-'a'])
query(root->next[name[0]-'a'],name+1);
return 0;
}
int n,m;
char str[100];
bool cmp(const int &a,const int &b)
{
return a < b;
}
int main()
{
int i,j,k;
while(scanf("%d%d",&n,&m)!=EOF)
{
pos=0;
init(&re_root);
global_num=1;
for(i=0;i<n;i++)
{
//global_num=i+1;
scanf("%s",str);
insert_trie(&re_root,str);
}
for(i=0;i<m;i++)
{
ans_pos=0;
scanf("%s",str);
query(&re_root,str);
if(ans_pos==0)
printf("Not match");
else
{
sort(ans,ans+ans_pos,cmp);
printf("%d",ans[0]-1);
for(j=1;j<ans_pos;j++)
if(ans[j]!=ans[j-1])
printf(" %d",ans[j]-1);
}
printf("\n");
}
}
return 0;
}这篇关于POJ 1816 Wild Words（trie 树上的DFS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
