POJ 2001 Shortest Prefixes 【Trie树】

题目大意：

找出能唯一标示一个字符串的最短前缀，如果找不出，就输出该字符串。

解题分析：

Trie树的简单应用，对于每个单词的插入，都在相应字符对应的节点 num 值+1 ，这样在查询的时候，如果遍历到num值为1的节点，就可以确定，该前缀能够唯一确定一个字符串，或者是一直遍历到NULL,这时直接输出它本身即可。

指针式Trie树：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int N =1e3+10;
 7 char word[N][26];
 8 struct Node{
 9     int num;
10     Node *next[26];
11     Node(){
12         num=0;
13         for(int i=0;i<26;i++)
14             next[i]=NULL;
15     }
16 };
17 Node *root;
18 Node *now,*newnode;
19 void Insert(char *str){
20     now=root;
21     for(int i=0;i<strlen(str);i++){
22         int to=str[i]-'a';
23         if(now->next[to]==NULL){   //如果该节点为空
24             newnode=new Node;
25             ++(newnode->num);
26             now->next[to]=newnode;
27             now=now->next[to];
28         }
29         else{
30             now=now->next[to];   
31             ++(now->num);
32         }
33     }
34 }
35 void Search(char *str){
36     char ans[26];
37     now=root;
38     for(int i=0;i<strlen(str);i++){
39         int to=str[i]-'a';
40         now=now->next[to];
41         ans[i]=str[i];    //ans[]记录下前缀字符串
42         ans[i+1]='

POJ 2001 Shortest Prefixes 【Trie树】

相关推荐