HDU 1277 全文检索 (Trie树应用 好题)

2024-03-20 14:32

本文主要是介绍HDU 1277 全文检索 (Trie树应用 好题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

全文检索

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 1304    Accepted Submission(s): 416

Problem Description
我们大家经常用google检索信息,但是检索信息的程序是很困难编写的;现在请你编写一个简单的全文检索程序。
问题的描述是这样的:给定一个信息流文件,信息完全有数字组成,数字个数不超过60000个,但也不少于60个;再给定一个关键字集合,其中关键字个数不超过10000个,每个关键字的信息数字不超过60个,但也不少于5个;两个不同的关键字的前4个数字是不相同的;由于流文件太长,已经把它分成多行;请你编写一个程序检索出有那些关键字在文件中出现过。
 

Input
第一行是两个整数M,N;M表示数字信息的行数,N表示关键字的个数;接着是M行信息数字,然后是一个空行;再接着是N行关键字;每个关键字的形式是:[Key No. 1] 84336606737854833158。
 

Output
输出只有一行,如果检索到有关键字出现,则依次输出,但不能重复,中间有空格,形式如:Found key: [Key No. 9] [Key No. 5];如果没找到,则输出形如:No key can be found !。
 

Sample Input
  
20 10 646371829920732613433350295911348731863560763634906583816269 637943246892596447991938395877747771811648872332524287543417 420073458038799863383943942530626367011418831418830378814827 679789991249141417051280978492595526784382732523080941390128 848936060512743730770176538411912533308591624872304820548423 057714962038959390276719431970894771269272915078424294911604 285668850536322870175463184619212279227080486085232196545993 274120348544992476883699966392847818898765000210113407285843 826588950728649155284642040381621412034311030525211673826615 398392584951483398200573382259746978916038978673319211750951 759887080899375947416778162964542298155439321112519055818097 642777682095251801728347934613082147096788006630252328830397 651057159088107635467760822355648170303701893489665828841446 069075452303785944262412169703756833446978261465128188378490 310770144518810438159567647733036073099159346768788307780542 503526691711872185060586699672220882332373316019934540754940 773329948050821544112511169610221737386427076709247489217919 035158663949436676762790541915664544880091332011868983231199 331629190771638894322709719381139120258155869538381417179544 000361739177065479939154438487026200359760114591903421347697[Key No. 1] 934134543994403697353070375063 [Key No. 2] 261985859328131064098820791211 [Key No. 3] 306654944587896551585198958148 [Key No. 4] 338705582224622197932744664740 [Key No. 5] 619212279227080486085232196545 [Key No. 6] 333721611669515948347341113196 [Key No. 7] 558413268297940936497001402385 [Key No. 8] 212078302886403292548019629313 [Key No. 9] 877747771811648872332524287543 [Key No. 10] 488616113330539801137218227609
 

Sample Output
  
Found key: [Key No. 9] [Key No. 5]
 
Author
Cai Minglun
 
Source
杭电ACM集训队训练赛(VI)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1277

题目分析:网上貌似都是ac自动机搞的,这里用trie树搞一下,跑了62ms,读入用getchar记录下换行次数,对key字符串建字典树,枚举流文件的后缀到字典树中查找,再用hash标记一下


#include <cstdio>
#include <cstring>
char t[60005], tmp[10], key[65];
bool hash[60005];struct node
{node *next[10];int id;node(){memset(next, NULL, sizeof(next));id = -1;}
};void Insert(node *p, char *s, int id)
{for(int i = 0; s[i] != '\0'; i++){int idx = s[i] - '0';if(p -> next[idx] == NULL)p -> next[idx] = new node();p = p -> next[idx];}p -> id = id;
}void Search(node *p, char *s)
{for(int i = 0; s[i] != '\0'; i++){int idx = s[i] - '0';if(p -> id != -1 && !hash[p -> id]){printf(" [Key No. %d]", p -> id);hash[p -> id] = true;}if(p -> next[idx] == NULL)return;p = p -> next[idx];}
}int main()
{int n, m, cnt1 = 0, cnt2 = 0;scanf("%d %d", &m, &n); getchar();while(cnt2 < m){char ch = getchar();if(ch == '\n')cnt2++;elset[cnt1++] = ch;}t[cnt1] = '\0';node *root = new node();memset(hash, false, sizeof(hash));for(int i = 1; i <= n; i++){//tmp读取"[Key","No.","1] "这些没用字符串scanf("%s%s%s%s", tmp, tmp, tmp, key);Insert(root, key, i);}printf("Found key:");for(int i = 0; t[i] != '\0'; i++)Search(root, t + i);printf("\n");
}


这篇关于HDU 1277 全文检索 (Trie树应用 好题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/829775

相关文章

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

水位雨量在线监测系统概述及应用介绍

在当今社会,随着科技的飞速发展,各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中,水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术,其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成,形成了一个完整的闭环系统。 数据采集单元:这是系统的“眼睛”,

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

zoj3820(树的直径的应用)

题意:在一颗树上找两个点,使得所有点到选择与其更近的一个点的距离的最大值最小。 思路:如果是选择一个点的话,那么点就是直径的中点。现在考虑两个点的情况,先求树的直径,再把直径最中间的边去掉,再求剩下的两个子树中直径的中点。 代码如下: #include <stdio.h>#include <string.h>#include <algorithm>#include <map>#

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s