1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 #define maxnode 1000 6 #define sigma_size 30 7  8 //struct Trie 9 //{10     int ch[maxnode][sigma_size];        //ch[i][j]：记录结点i的那个编号为j的子节点11     int val[maxnode];                    //val[i]：i节点的附加信息，这里我们用来记录是否到一个单词的结束12                                         //（即在trie树上root->i一路下来是否是一个完整的单词）13     int sz;14     void Trie()15     {16         sz=1;17         memset(ch[0],0,sizeof(ch[0]));18     }19     int idx(char c)                       //idx(c)即字符c的编号。20     {21         return c-‘0‘;                    //此处第一个字符是0所以return c-‘0‘22     }23     void Insert(string s,int v)24     {25         int u=0,n=s.length();26         for (int i=0;i<n;i++)27         {28             int c=idx(s[i]);29             if (!ch[u][c])30             {31                 memset(ch[sz],0,sizeof(ch[sz]));32                 val[sz]=0;33                 ch[u][c]=sz++;34             }35             u=ch[u][c];36         }37         val[u]=v;38     }39     bool query(string s)     //true:s is a prefix40     {41         int u=0,c;42         for (int i=0;i<s.length();i++)43         {44             c=s[i]-‘0‘;45             if (!ch[u][c])    return false;46 47             u=ch[u][c];48             if (val[u]==1)  return true;    //若此时s还没走完但trie树上已经走到结尾了，即树上单词是s的前缀49         }50         return true;51     }52 //};53 54 bool ok;55 string str;56 57 int main()58 {59     //freopen("in.txt","r",stdin);60 61     ok=true;62     Trie();63     int num=0;64     while (cin>>str)65     {66         if (str=="9")67         {68             num++;69             if (ok)70                 printf("Set %d is immediately decodable\n",num);71             else72                 printf("Set %d is not immediately decodable\n",num);73             ok=true;74             Trie();75         }76         else77         {78             if (query(str))79                 ok=false;80             Insert(str,1);81         }82     }83 }