POJ　1156 IMMEDIATE DECODABILITY 解题报告

时间：2010-04-25 来源：MC_ACM

问题描述

http://acm.pku.edu.cn/JudgeOnline/problem?id=1056

Sample Input

0010

0000

010

0000

Sample Output

Set 1 is immediately decodable

Set 2 is not immediately decodable

题意：

输入一组数，判断是否存在某个数是另外一个数的前缀。

Trie树的性质：

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同。

解题思路：

使用trie树。

代码：

#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 ;
}