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

比较麻烦的trie。

首先你需要选择针对n还是m建立trie,这里我选择了针对n。

那么就需要面临卡空间的问题。

这里提供了一种链式前向星的方法能够当你不会指针trie的时候卡过空间。(做法看代码吧)

然后针对m进行在trie上的dfs即可。

对于相同字符或?来说,trie下移1位,匹配串移动1位。

对于*来说,trie下移,匹配串移动0~长度位。

(合计这道题就难在模拟上了)

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=;
char s[];
struct node{
char se;
int to;
int nxt;
vector<int>ed;
}edge[maxn];
int head[maxn],cnt=,cnt1=;
void add(int u,char c){
cnt++;cnt1++;
edge[cnt].se=c;
edge[cnt].to=cnt1;
edge[cnt].nxt=head[u];
head[u]=cnt;
return;
}
void insert(int k){
int u=;
int l=strlen(s);
for(int i=;i<l;i++){
int v=-;
char c=s[i];
for(int j=head[u];j;j=edge[j].nxt){
if(edge[j].se==c){
v=edge[j].to;
if(i==l-)edge[j].ed.push_back(k);
break;
}
}
if(v<){
add(u,c);
v=cnt1;
if(i==l-)edge[cnt].ed.push_back(k);
}
u=v;
}
return;
}
vector<int>ans;
int l;
void check(int u,int k,int p){
if(k==l){
if(!edge[p].ed.empty()){
for(int i=;i<edge[p].ed.size();i++){
ans.push_back(edge[p].ed[i]);
}
}
for(int j=head[u];j;j=edge[j].nxt){
int v=edge[j].to;
if(edge[j].se=='*'){
check(v,k,j);
}
}
return;
}
char c=s[k];
for(int j=head[u];j;j=edge[j].nxt){
int v=edge[j].to;
if(edge[j].se==c||edge[j].se=='?'){
check(v,k+,j);
}
if(edge[j].se=='*'){
for(int q=;q<=l-k;q++){
check(v,k+q,j);
}
}
}
return;
}
bool t[];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<n;i++){
scanf("%s",s);
insert(i);
}
for(int j=;j<m;j++){
scanf("%s",s);
ans.clear();
l=strlen(s);
check(,,);
if(ans.empty()){
printf("Not match");
}else{
memset(t,,sizeof(t));
sort(ans.begin(),ans.end());
for(int i=;i<ans.size();i++){
if(!t[ans[i]]){
printf("%d ",ans[i]);
t[ans[i]]=;
}
}
}
printf("\n");
}
return ;
}

最新文章

  1. JavaScript 数据属性和访问器属性
  2. C/C++函数调用的几种方式及函数名修饰规则以及c++为什么不允许重载仅返回类型不同的函数
  3. Python之RabbitMQ操作
  4. ahjesus C# 4.0 Parallel 并行运算
  5. iOS深入学习(UITableView:系列1-最基本的东西)
  6. web.py网页模板中使用jquery
  7. Linux ssh安全设置
  8. 运行一个android程序,直接访问某个网站
  9. Leetcode_001_TwoSum_求和为固定数的两个数的索引
  10. CentOS下安装JDK的三种方法
  11. Android4.0-4.4 加入支持状态栏显示耳机图标方法(支持带不带MIC的两种耳机自己主动识别)
  12. INITTAB 配置文件
  13. 项目中的导出(jxl插件)
  14. rocketmq番外篇(一):开发命令行
  15. Android 几种网络请求的区别与联系
  16. fstat函数
  17. EF(二)Model Fiirst
  18. Combat 战斗任务
  19. Linux裸设备管理详解--
  20. python之路(十七)-javascript

热门文章

  1. centos配置ip地址 添加多个ip地址的方法
  2. 韦大仙--python对文件操作
  3. Java学习笔记-13.创建窗口和程序片
  4. 从零开始的Python学习Episode 3——字符串格式化与for循环
  5. Ext JS 6学习文档-第5章-表格组件(grid)
  6. Sublime Text 插件之:MarkDown
  7. oracle数据库之存储函数和过程
  8. (转)apktool+dex2jar+jd_gui
  9. 在mysql启用远程连接
  10. Ansys Workbench热流固耦合仿真配置