题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1277
题目大意及思路:和前一个题相同,只是这个题要求输出id。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 11000
char s[60010],str[66];
int ans[1010],rec;
char st[60010];
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a<b?a:b;
}
int q[Max*60],cnt;
struct node
{
int id,fail;
int next[10];
void init()
{
id=fail=0;
memset(next,0,sizeof(next));
}
}tri[Max*60];
void insert(char *s,int num)
{
int i,p,id;
p=0;
for(i=0;s[i];i++)
{
id=s[i]-'0';
if(!tri[p].next[id])
{
tri[++cnt].init();
tri[p].next[id]=cnt;
}
p=tri[p].next[id];
}
tri[p].id=num;
}
void bfs()
{
int i,id,suf,p,head,tail;
p=0;head=tail=0;
for(i=0;i<10;i++)
{
if(tri[0].next[i])
{
q[tail++]=tri[0].next[i];
tri[q[tail-1]].fail=0;
}
else
tri[0].next[i]=0;
}
while(head<tail)
{
//printf("akkkk");
p=q[head++];suf=tri[p].fail;
for(i=0;i<10;i++)
{
if(tri[p].next[i])
{
q[tail++]=tri[p].next[i];
tri[q[tail-1]].fail=tri[suf].next[i];
}
else
{
tri[p].next[i]=tri[suf].next[i];
}
}
}
}
int query(char *s)
{
int i,id,p,tmp;
p=0;
for(i=0;s[i];i++)
{
id=s[i]-'0';
p=tri[p].next[id];
tmp=p;
if(tmp&&tri[tmp].id!=-1)
{
if(tri[tmp].id)
ans[rec++]=tri[tmp].id;
tri[tmp].id=-1;
tmp=tri[tmp].fail;
}
}
return rec;
}
int main()
{
int n,m,i;
while(scanf("%d%d",&m,&n)!=EOF)
{
s[0]=0;
tri[0].init();
cnt=0;
rec=0;
while(m--)
{
scanf("%s",st);
strcat(s,st);
}
// printf("%s\n",s);
for(i=1;i<=n;i++)
{
scanf("%s%s%s%s",str,str,str,str);
insert(str,i);
}
bfs();
if(query(s)==0)
puts("No key can be found !");
else
{
printf("Found key:");
for(i=0;i<rec;i++)
{
printf(" [Key No. %d]",ans[i]);
}
puts("");
}
}
}
分享到:
相关推荐
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
杭州电子科技大学oj平台上的第1010题,是关于搜索的题目,很不错的题
搜索 dfs 解题代码 hdu1241
NULL 博文链接:https://128kj.iteye.com/blog/1734821
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 (lecture_...
HDU的ACM,非常的好 涉及了很多算法,例如二分匹配、博弈、组合、最小生成树、搜索、动态规划、贪心算法
HDUACM201303版_10搜索入门
经典算法:(二分匹配,背包专题,筛选法,简单数学题,贪心算法,递推求解,动态规划,并查集,母函数,搜索,组合博弈等入门算法)
杭电ACM课件2014版之HDUACM201403版_10)搜索入门
一款 HDU OJ 的自动刷题工具,搜索来源可选用 百度搜索 / 必应搜索,支持并行以及串行查找,祝早日刷上航电首页哦~ 使用 Python 编写,执行之前你需要在同目录下创建文件 aclog.txt ,然后粘贴进你目前已经 AC 的...
ACM培训好资料!能帮助你快速提高ACM AC题目的能力,值得一下
acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs
本压缩包内包含杭电ACM集训的课件PPT,较为详细的介绍了动态规划,计算几何,贪心算法, 搜索,二分图及其应用,母函数及其应用,组合博弈入门,并查集,递推求解等常用算法
08暑假集训搜索组解题报告 An Introduction to Recursion, Part 1.mht An Introduction to Recursion, Part 2.mht ...搜索入门 - from hdu.ppt 搜索算法的通用优化方法.pdf 谈搜索算法的剪枝优化.pdf
(HDUACM2010版_11)搜索入门,提供 (HDUACM2010版_11)搜索入门供参考
其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的 和
应同学之邀帮忙发布的一篇勘误 【HDU 3993】田忌赛马 题解+勘误 题解这里就略写一下了,主要是勘误。 这道题是2011年之前的多校...数据很小,可以考虑状态压缩+记忆化搜索 直接定义二维状态有很多浪费的空间,可以考虑u
acm搜索 6题 代码 hdu 1181 1312 1015 1010 1241 1372
资源大小:66.8M ...在地址栏键入字词或网址即可获得有关搜索和网页的建议。 2.常用网站的缩略图 从任一新标签即刻访问您最喜爱的网页。 3.应用程序的快捷方式 为您最喜爱的网络应用程序创建桌面快捷方式。
爬虫(Spider)这个词相信大家都听说过,从网页搜索引擎,饭圈刷数据,到秒杀Any抢不到的格裙,都是爬虫的具体实现 这个概念一听就很nb,但是今天我通过这篇文章来让大家大致对它有个认识,甚至能自己实现一个基础的...