POJ 1056 IMMEDIATE DECODABILITY 【Trie树】

题目大意：
给你几段只包含0,1的序列，判断这几段序列中，是否存在至少一段序列是另一段序列的前缀。

解题分析：

Trie树水题，只需要在每次插入字符串，并且在Trie树上创建节点的时候，判断路径上是否已经有完整的单词出现即可。

数组版：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 char word[15];
 6 bool flag;
 7 int trie[10*15][2],cnt,ncase;
 8 bool fp[10*15];
 9 void Init(){
10     flag=true;
11     cnt=0;
12     memset(fp,false,sizeof(fp));
13     memset(trie,0,sizeof(trie));
14 }
15 void Insert(char *str){
16     int now=0;
17     for(int i=0;i<strlen(str);i++){
18         int to=str[i]-'0';
19         if(!trie[now][to]){
20             trie[now][to]=++cnt;
21         }
22         now=trie[now][to];
23         if(fp[now])flag=false;
24     }
25     fp[now]=true;
26 }
27 int main(){
28     ncase=0;
29     Init();
30     while(gets(word)){
31         if(word[0]=='9'){
32             if(flag)printf("Set %d is immediately decodable
",++ncase);
33             else printf("Set %d is not immediately decodable
",++ncase);
34             Init();
35             continue;
36         }
37         Insert(word);
38     }
39 }

指针版：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 char word[15];
 7 bool flag;
 8 struct Node{
 9     bool fp;
10     Node *next[2];
11     Node(){
12         fp=false;
13         for(int i=0;i<2;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]-'0';
23         if(now->next[to]==NULL){
24             now->next[to]=new Node;
25         }
26         now=now->next[to];
27         if(now->fp==true)flag=false;   //如果路径上出现过完整的单词，则说明不符合 
28     }
29     now->fp=true;
30 }
31 int main(){
32     flag=true;int ncase=0;
33     root=new Node;
34     while(gets(word)){
35         if(word[0]=='9'){
36             if(flag)printf("Set %d is immediately decodable
",++ncase);
37             else printf("Set %d is not immediately decodable
",++ncase);
38             flag=true;
39             root=new Node;
40             continue;
41         }
42         Insert(word);
43     }
44     return 0;
45 }

2018-10-30

POJ 1056 IMMEDIATE DECODABILITY 【Trie树】

相关推荐