http://poj.org/problem?id=1056

Trie

有一些字符串，判断是否：这些字符串之间都不是彼此的前缀

1 #include 
     
       2 #include 
      
        3  4 const int CHARSET = 2, BASE = '1', MAX_NODE = 1001;  5  6 int tot, root, child[MAX_NODE][CHARSET]; 7 bool flag[MAX_NODE]; 8  9 void init()10 {11     memset(child, 0, sizeof(child));12     flag[1] = false;13     root = tot = 1;14 }15 16 int insert(const char *str)17 {18     int i, cur, j, flag1 = 0, flag2 = 0;19     cur = root;20     for(i=0; str[i]; i++)21     {22         if(child[cur][str[i]-BASE] == 0)23         {24             if(flag[cur])25             {26                 flag2 = 1;27             }28             flag1 = 1;29             tot = tot + 1;30             child[cur][str[i]-BASE] = tot;31             memset(child[tot], 0, sizeof(child[tot]));32             flag[tot] = false;33         }34         cur = child[cur][str[i]-BASE];35     }36     flag[cur] = true;37     if(flag1 == 0 || flag2 == 1)38     {39         return 1;//重复 40     }41     return 0;42 }43 44 45 46 int main()47 {48     char s[12] = "\0";49     int cases = 1, temp, flag = 0;50     init();51     while(~scanf("%s", s))52     {53         if(strcmp(s, "9") == 0)54         {55             if(flag)56             {57                 printf("Set %d is not immediately decodable\n", cases);58             }59             else60             {61                 printf("Set %d is immediately decodable\n", cases);62             }63             cases ++;64             flag = 0;65             init();66         }67         else68         {69             temp = insert(s);70             //printf("%d\n", temp);71             flag |= temp;72         }73         memset(s, 0, sizeof(s));74     }75     return 0;76 }