ZOJ 1808 Immediately Decodable

字典树较简单题，无需维护标记，注意细节即可。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 100027

struct node
{
    node *next[2];
}*root;
char ss[10][13];

node *create()
{
    node *p;
    p = (node *)malloc(sizeof(node));
    for(int i=0;i<2;i++)
        p->next[i] = NULL;
    return p;
}

void release(node *p)
{
    for(int i=0;i<2;i++)
    {
        if(p->next[i] != NULL)
            release(p->next[i]);
    }
    free(p);
}

void insert(char *ss)
{
    node *p = root;
    int i = 0,k;
    while(ss[i])
    {
        k = ss[i++] - '0';
        if(p->next[k] == NULL)
            p->next[k] = create();
        p = p->next[k];
    }
}

bool search(char *ss)
{
    node *p = root;
    int i = 0,k;
    while(ss[i])
    {
        k = ss[i++] - '0';
        p = p->next[k];
    }
    if(p->next[0] != NULL || p->next[1] != NULL)
        return false;
    return true;
}

int main()
{
    int cs = 1,k,i,j,flag;
    root = create();
    i = k = 0;
    while(scanf("%s",ss[i])!=EOF)
    {
        if(ss[i][0] == '9')
        {
            if(k == 0)  //如果此时没有建树
            {
                printf("Set %d is immediately decodable
",cs++);
                continue;
            }
            flag = 1;
            for(j=0;j<i;j++)
            {
                if(!search(ss[j]))
                {
                    flag = 0;
                    break;
                }
            }
            if(flag)
                printf("Set %d is immediately decodable
",cs++);
            else
                printf("Set %d is not immediately decodable
",cs++);
            i = k = 0;
            release(root);
            root = create();
        }
        else
        {
            insert(ss[i]);
            k = 1;
            i++;
        }
    }
    release(root);
    return 0;
}