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

题意:给你n个模板串,然后每个串除了字母,还有?或者*,?可以代替任何非空单个字符,*可以替代任何长度任何串,包括空字符串。现在给以一些串,问你这些串在哪些串中出现过。

题解:trie+DFS。首先,把n个字符串放到trie中,注意,这n个串中可能有相同的字符串。然后对于每个要查询的串,从根节点进行DFS搜索,注意一些特殊处理,例如匹配到*或者?的处理。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 500001
using namespace std;
const int cha=;
struct node{
int num;
int count[];//从根到此处是否是关键字,并且记录是多少个关键字的结尾
int next[cha];
}tree[N];
int ans[],top;
int n,m;
void init(node &a,int data){
a.num=;
for(int i=;i<cha;i++)
a.next[i] = -;
}
int k = ;
void insert(char s[],int num){
int p = ;
for(int i=;s[i];i++){
int data = s[i]-'a';
if(s[i]=='?')data=;
if(s[i]=='*')data=;
if(tree[p].next[data]==-){//不存在该结点
init(tree[k],num);
tree[p].next[data] = k;
k++;
}
p = tree[p].next[data];
}
int temp=tree[p].num;
tree[p].num++;
tree[p].count[++temp]=num;
}
void DFS(node p,char *s,int len,int cur){
if(cur==len){
if(p.num){
for(int i=;i<=p.num;i++)
ans[++top]=p.count[i];
}
while(p.next[]>&&tree[p.next[]].num==)
p=tree[p.next[]];
if(p.next[]>&&tree[p.next[]].num>){
int tt=tree[p.next[]].num;
for(int i=;i<=tt;i++)
ans[++top]=tree[p.next[]].count[i];
}
return ;
}
int t=s[cur]-'a';
if(p.next[t]>)
DFS(tree[p.next[t]],s,len,cur+);
if(p.next[]>)
DFS(tree[p.next[]],s,len,cur+);
if(p.next[]>){
int temp=cur;
while(temp<=len){
DFS(tree[p.next[]],s,len,temp);
temp++;
}
}
}
char str[];
int main(){
while(~scanf("%d%d",&n,&m)){
init(tree[],-);
for(int i=;i<=n;i++){
scanf("%s",str);
insert(str,i-);
}
for(int i=;i<=m;i++){
scanf("%s",str);
top=;
DFS(tree[],str,strlen(str),);
sort(ans+,ans+top+);
int tt=unique(ans+,ans+top+)-ans-;
if(tt>){
for(int i=;i<tt;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[tt]);
}
else
printf("Not match\n");
}
}
}

最新文章

  1. win32记事本程序(二)
  2. IS A 和 HAS A的区别
  3. 数据库存储txt文本和jpg图片
  4. xml基础学习笔记04
  5. .a与.framework的区别
  6. Spring基础复习
  7. 《Redis入门指南》第2版 读书笔记
  8. SpringCloud微框架系列整体模块梳理
  9. Hibernate查询以及优化策略04
  10. AtCoder Regular Contest 080 (ARC080) E - Young Maids 线段树 堆
  11. Bzoj4598: [Sdoi2016]模式字符串 点分治 哈希
  12. C++类模板和模板类
  13. 牛客OI赛制测试赛3游记
  14. 【Java】阿里巴巴Java开发手册(纪念版)
  15. Android静默安装实现方案,仿360手机助手秒装和智能安装功能
  16. wxWidgets:菜单
  17. pthread_cond_wait()函数的详解
  18. Jenkins+Sonar集成对代码进行持续检测
  19. Visual Studio Code 之 运行java代码
  20. Java代码规范、基本类型和实例演练

热门文章

  1. c++基础语法 构造函数 析构函数 类的组合
  2. find which process occupy the PORT
  3. JMS—事务管理
  4. 《转》手把手教你使用Git
  5. Modelsim覆盖率
  6. w3c 学习html DOM
  7. 在masterpage中添加对usercontrol的引用
  8. WildFly 9.0.2+mod_cluster-1.3.1 集群配置
  9. MVC小系列(二十)【给Action提供HttpStatusCodeResult】
  10. 再跟SQL谈一谈--基础篇