|
#include <iostream>
#include <string>
using namespace std ;
struct trie{
struct trie *son[2] ;
int flag ; //终止位
} *root ;
const int size=10+2 ;
char str[size] ;
int isterminal ; //判断路线是否走过
trie *NewTrie()
{
trie *temp=new trie;
for(int i=0;i<2;i++)
{
temp->son[i]=NULL;
}
temp->flag=0;
return temp;
}
void insert()
{
int i, j ,len;
trie *p=root, *q ;
len=strlen(str);
for( i=0; i<len; ++i ){
j = str[i]-'0' ;
if( p->son[j] == NULL ){
isterminal = 0 ; //一条不存在的路径
q = NewTrie();
p->son[j] = q ;
}
p = p->son[j] ;
if( p->flag ) // 如果有一个单词的前缀是当前插入单词的前缀，则返回
return ;
}
p->flag = 1 ;
}
int main()
{
int cases,result;
cases=0;
result=1;
root = NewTrie();
while(scanf("%s", str)!=EOF ){
if( str[0]=='9'){
if( result )
printf("Set %d is immediately decodable\n", ++cases ) ;
else
printf("Set %d is not immediately decodable\n", ++cases ) ;
root = NewTrie();
result = 1 ;
continue ;
}
isterminal = 1 ; //插入的时候是一条已存在的路径，则不行
insert() ;
if( isterminal == 1 )
result = 0 ;
}
return 0 ;
}
|
