专栏首页mlhdu----(2222)Keywords Search(trie树)

hdu----(2222)Keywords Search(trie树)

Keywords Search

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 35683    Accepted Submission(s): 11520

Problem Description

In the modern time, Search engine came into the life of everybody like Google, Baidu, etc. Wiskey also wants to bring this feature to his image retrieval system. Every image have a long description, when users type some keywords to find the image, the system will match the keywords with description of image and show the image which the most keywords be matched. To simplify the problem, giving you a description of image, and some keywords, you should tell me how many keywords will be match.

Input

First line will contain one integer means how many cases will follow by. Each case will contain two integers N means the number of keywords and N keywords follow. (N <= 10000) Each keyword will only contains characters 'a'-'z', and the length will be not longer than 50. The last line is the description, and the length will be not longer than 1000000.

Output

Print how many keywords are contained in the description.

Sample Input

1 5 she he say shr her yasherhs

Sample Output

3

Author

Wiskey

代码:

字典树

 1 /*hdu 2222 字典树*/
 2 //#define LOCAL
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<iostream>
 6 using namespace std;
 7 struct Trie
 8 {
 9    struct Trie *next[26];
10    int tail;
11 };
12 char str[55];
13 char ss[1000005];
14 void in_Trie(char *s,Trie *root)
15 {
16    Trie *cur=root,*newcur;
17   for(int i=0;s[i]!='\0';i++)
18   {
19        if(cur->next[s[i]-'a']==NULL)
20      {
21          newcur=new Trie;   //(Trie*)malloc(sizeof(sizeof(Trie)));
22          for(int j=0;j<26;j++)
23            newcur->next[j]=NULL;
24             newcur->tail=0;
25         cur->next[s[i]-'a']=newcur;
26      }
27     cur=cur->next[s[i]-'a'];
28   }
29    cur->tail++;
30 }
31 int query(char *s,Trie *root)
32 {
33     int i=0,cnt=0;
34     Trie *cur;
35     for(int j=0;s[j]!='\0';j++)
36     {
37         cur=root;
38       for(i=j;s[i]!='\0';i++){
39         if(cur->next[s[i]-'a']!=NULL){
40          cur=cur->next[s[i]-'a'];
41             cnt+=cur->tail;
42             cur->tail=0;  //只需求出第一次出现的
43         }
44        else  break;
45       }
46     }
47    return cnt;
48 }
49 void dele(Trie *root)
50 {
51   for(int i=0 ; i<26 ; i++ )
52       if(root->next[i]!=NULL)
53       dele(root->next[i]);
54  // free(root);
55  delete root;
56 }
57 int main()
58 {
59   #ifdef LOCAL
60   freopen("test.in","r",stdin);
61   #endif
62   int t,i,n;
63   Trie *root;
64   scanf("%d",&t);
65   while(t--)
66   {
67        root = new Trie ;
68        for(int j=0;j<26;j++)
69        root->next[j]=NULL;
70        root->tail=0;
71      scanf("%d",&n);
72     for(i=0;i<n;i++){
73       scanf("%s",str);
74       in_Trie(str,root);
75     }
76     scanf("%s",ss);
77     printf("%d\n",query(ss,root));
78     dele(root);
79     }
80    return 0;
81 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C语言最难啃的三块硬骨头

    提到C语言很多初学者都觉得,学到中间就进行不下去了,因为碰到了几个硬骨头死活翻不过去,于是很多人给C语言下结论太难了,太靠近底层了,特别是那几块难啃的骨头,直接...

    程序员互动联盟
  • 读 Java Arrays 源码 笔记

    Arrays.java是Java中用来操作数组的类。使用这个工具类可以减少平常很多的工作量。了解其实现,可以避免一些错误的用法。 它提供的操作包括: 排序 so...

    程序员互动联盟
  • mysql几种存储引擎介绍

    前言 在数据库中存的就是一张张有着千丝万缕关系的表,所以表设计的好坏,将直接影响着整个数据库。而在设计表的时候,我们都会关注一个问题,使用什么存储引擎。等一下...

    学到老
  • 八大排序算法

    排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说...

    程序员互动联盟
  • 数据结构是哈希表(hashTable)(二)

    public class HashTableDouble { private DataItem[] hashArray; privat...

    奋斗蒙
  • SPSS Modeler 介绍决策树

    本文将通过 SPSS Modeler 介绍决策树 (Decision tree) 演算法于银行行销领域的应用实例。通过使用网路公开电销资料建立不同决策树模型,分...

    学到老
  • Gnuboard 漏洞分析

    Gnuboard是韩国Sir公司开发一套PHP+Mysql CMS程序。 本身数据结构简单,可扩展性能强,程序运行代码与皮肤文件分离,可扩展数据字段多,可以进行...

    Seebug漏洞平台
  • 【C语言系列】C语言概念--基本数据类型简介

    1.概述   C 语言包含的数据类型如下图所示: ? 2.各种数据类型介绍 2.1整型   整形包括短整型、整形和长整形。 2.1.1短整形   short ...

    程序员互动联盟
  • 干货 | JAVA反序列化安全实例解析

    作者简介 迟长峰,携程技术中心信息安全部应用安全工程师。 什么是序列化 序列化 (Serialization)是指将对象的状态信息转换为可以存储或传输的形式的过...

    用户1292807
  • 数据结构是哈希表(hashTable)(一)

    哈希表也称为散列表,是根据关键字值(key value)而直接进行访问的数据结构。也就是说,它通过把关键字值映射到一个位置来访问记录,以加快查找的速度。这个映射...

    奋斗蒙

扫码关注云+社区

领取腾讯云代金券