点击打开链接hdu 1277
思路:AC自动机模板题
分析:
1 只要把输入处理成一个字符串,然后对关键字建立trie树和求next
2 注意题目是说按照匹配到的顺序输出,所以这个地方注意一下。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define MAXN 600010
#define MAX 10010
#define N 15
int n , m , cnt;
char text[MAXN];
struct Node{
Node *next;
Node *child[N];
int number;
};
Node node[MAXN];
Node *root;
queue<Node*>q;
Node* newNode(){
node[cnt].next = NULL;
node[cnt].number = 0;
for(int i = 0 ; i < N ; i++)
node[cnt].child[i] = NULL;
return &node[cnt++];
}
void insert(char *str , int x){
int len = strlen(str);
Node *p = root;
for(int i = 0 ; i < len ; i++){
int num = str[i]-'0';
if(p->child[num] == NULL)
p->child[num] = newNode();
p = p->child[num];
}
p->number = x;
}
void getNext(){
while(!q.empty())
q.pop();
q.push(root);
root->next = NULL;
while(!q.empty()){
Node *p = q.front();
q.pop();
for(int i = 0 ; i < N ; i++){
if(p->child[i]){
q.push(p->child[i]);
Node *tmp = p->next;
while(tmp){
if(tmp->child[i]){
p->child[i]->next = tmp->child[i];
break;
}
tmp = tmp->next;
}
if(tmp == NULL)
p->child[i]->next = root;
}
}
}
}
bool find(){
int len = strlen(text);
bool mark = false;
Node *p = root;
for(int i = 0 ; i < len ; i++){
int num = text[i]-'0';
while(p->child[num] == NULL && p != root)
p = p->next;
if(p->child[num]){
p = p->child[num];
Node *tmp = p;
while(tmp){
if(tmp->number){
if(!mark){
printf("Found key:");
mark = true;
}
printf(" [Key No. %d]" , tmp->number);
}
tmp = tmp->next;
}
}
}
return mark;
}
int main(){
char str[MAXN];
while(scanf("%d%d%*c" , &n , &m) != EOF){
cnt = 0;
root = newNode();
for(int i = 0 ; i < n ; i++){
gets(str);
strcat(text , str);
}
int len = strlen(text);
text[len] = '\0';
gets(str);/*读掉空行*/
for(int i = 0 ; i < m ; i++){
gets(str);
for(int j = 1 ; j < n ; j++){
if(str[j] == ' ' && str[j-1] == ']'){
insert(str+j+1 , i+1);
break;
}
}
}
getNext();
if(!find())
printf("No key can be found !");
printf("\n");
}
return 0;
}
分享到:
相关推荐
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,但是今天我通过这篇文章来让大家大致对它有个认识,甚至能自己实现一个基础的...