全文检索

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

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]

题目大意：给定一段长数字串和一组短的数字串，问哪些短串在长串中出现过。

Trie 树

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <string>
  7 #include <vector>
  8 #include <stack>
  9 #include <queue>
 10 #include <set>
 11 #include <map>
 12 #include <iomanip>
 13 #include <cstdlib>
 14 using namespace std;
 15 const int INF=0x5fffffff;
 16 const int MS=100005;
 17 const double EXP=1e-8;
 18 
 19 struct node
 20 {
 21      int id;
 22     //bool have;
 23     node * next[10];
 24 }nodes[MS*10];   //注意这个大小  尽量大一点
 25 
 26 node *root;
 27 bool flag;
 28 int cnt;
 29 
 30 char text[MS];
 31 char key[100];
 32 bool mark[MS/10];
 33 node * add_node(int c)
 34 {
 35     node *p=&nodes[c];
 36     for(int i=0;i<10;i++)
 37         p->next[i]=NULL;
 38    // p->have=false;
 39     p->id=-1;
 40     return p;
 41 }
 42 
 43 void insert(char *str,int no)
 44 {
 45     node *p=root,*q;
 46     int len=strlen(str);
 47     for(int i=0;i<len;i++)
 48     {
 49         int id=str[i]-'0';
 50         if(p->next[id]==NULL)
 51         {
 52             q=add_node(cnt++);
 53             p->next[id]=q;
 54         }
 55         p=p->next[id];
 56     }
 57     p->id=no;
 58 }
 59 void search(char *str)
 60 {
 61     node *p=root;
 62     int len=strlen(str);
 63     for(int i=0;i<len;i++)
 64     {
 65         int id=str[i]-'0';
 66         p=p->next[id];
 67         if(p==NULL)
 68             return ;
 69         if(p->id!=-1&&mark[p->id]==false)
 70         {
 71             if(!flag)
 72             {
 73                 printf("Found key: [Key No. %d]",p->id);
 74                 flag=true;
 75                 mark[p->id]=true;
 76             }
 77             else
 78             {
 79                 printf(" [Key No. %d]",p->id);
 80                 mark[p->id]=true;
 81             }
 82         }
 83     }
 84 }
 85 
 86 int main()
 87 {
 88     int n,m,i,j,k=0;
 89     scanf("%d %d",&n,&m);
 90     char tstr[MS/100];
 91     flag=false;
 92     memset(mark,false,sizeof(mark));
 93     cnt=0;
 94     root=add_node(cnt++);
 95     for(i=0;i<n;i++)
 96     {
 97         scanf("%s",tstr);
 98         int len=strlen(tstr);   //用strcat更好。
 99         for(j=0;j<len;j++)
100             text[k++]=tstr[j];
101     }
102     text[k]='';
103     //getchar();  //可以加也可以不加，因为scanf()可以跳过换行符
104     for(i=0;i<m;i++)
105     {
106         scanf("%s%s%s%s",tstr,tstr,tstr,key);
107         insert(key,i+1);
108     }
109     for(i=0;i<k-4;i++)
110     {
111         search(text+i);
112     }
113     if(!flag)
114         printf("No key can be found !
");
115     else
116         printf("
");
117     return 0;
118 }