集训队专题（1）1001 Immediate Decodability

题意：判断一组数中是否存在一个数是另一个数的前缀。

输入：有多组数据，每组数据以数字‘9’作为结束。

输出：如果有就输出“Set # is not immediately decodable”，否则输出“Set # is immediately decodable”。

样例输入：

0110001000009011001000009
样例输出：
Set 1 is immediately decodableSet 2 is not immediately decodable
基础字典树，由于数据原因，当时是这样过的...
#include <bits/stdc++.h>using namespace std;int main(){    char str[20][20],temp[20];    int ansNum=1,cnt=0,i,j,flag=1,len,t;    while(~scanf("%s",temp))    {        if(temp[0]=='9')        {            for(i=1;i<cnt;i++)            {                if(!flag) break;                for(j=i+1;j<=cnt;j++)                {                    if(!flag) break;                    len=min(strlen(str[i]),strlen(str[j]));                    for(t=0;t<len;t++)                    {                        if(str[i][t]!=str[j][t])                        {                            flag=1;                            break;                        }                        flag=0;                    }                }            }            if(flag) PRintf("Set %d is immediately decodable/n",ansNum);            else printf("Set %d is not immediately decodable/n",ansNum);            cnt=0,flag=1,ansNum++;            memset(str,0,sizeof(str));        }        else        {            strcpy(str[++cnt],temp);            getchar();        }    }}
贴一个指针字典树的代码：
#include <cstdio>  #include <stdlib.h>  #include <string.h>  #include <iostream>  using namespace std;  struct TreeNode  {      int n;      TreeNode *next[2];      TreeNode()      {          for(int i=0; i<2; i++)          {              next[i] = NULL;          }          n=1;      }  };  void insert(char str[],TreeNode *pHead)  {      TreeNode *p = pHead;      int nLen=strlen(str);      for(int i=0; i<nLen; i++)      {          if(p->next[str[i]-'0'] == NULL)              p->next[str[i]-'0'] = new TreeNode;          else              p->next[str[i]-'0']->n++;          p = p->next[str[i]-'0'];      }  }  int search(char str[],TreeNode *pHead)  {      int nLen = strlen(str);      TreeNode *p=pHead;      bool bfind = false;      for(int i=0; i<nLen; i++)          p = p->next[str[i]-'0'];      return p->n;  }  void Delete(TreeNode *pHead)  {      for(int i=0; i<2; i++)      {          if(pHead != NULL)          {              pHead = pHead->next[i];              Delete(pHead);          }      }      delete pHead;  }  int main()  {      char str[10][15];      int nCase=0;      int n=-1;      TreeNode *pHead = new TreeNode;      int flag=0;      while(scanf("%s",str[++n])!=EOF)      {          if(str[n][0] == '9')          {              ++nCase;              for(int i=0; i<n; i++)              {                  if(search(str[i],pHead) > 1)                  {                      printf("Set %d is not immediately decodable/n",nCase);                      break;                  }                  if(i == n-1)                  {                      printf("Set %d is immediately decodable/n",nCase);                  }              }              Delete(pHead);              pHead = new TreeNode;              n = -1;          }          else          {              insert(str[n],pHead);          }      }      return 0;  }