misschuer

常用链接

统计

积分与排名

百事通

最新评论

统计难题 字典树 处女作

 

#include<iostream>
using namespace std;

struct t
{
  struct t *next[ 26 ];

  int num;
};


int main()
{
  int i;

   t * root = new t;
    
  for(i = 0 ; i < 26 ; ++ i)

      root->next[ i ] = NULL;

         root->num = 0;

   char c[ 11 ];

   char *cmp;

   while(cin.getline(c , 11) , c[ 0 ])
   {
       t * now = new t;

       now = root;

       cmp = c;

       while(*cmp)
       {

          if(now->next[*cmp - 'a'] == NULL)
          {
            now->next[*cmp - 'a'] = new t;

            now->next[*cmp - 'a']->num = 1;

            now = now->next[*cmp - 'a'];

            for(i = 0 ; i < 26 ; ++ i)

                now->next[ i ] = NULL;
          }

          else
          {

             now->next[*cmp - 'a']->num ++;
          
             now = now->next[*cmp - 'a'];
          }

          cmp ++;
       }


   }

   while(cin.getline(c , 11) , cin && c[ 0 ])
   {
     
    int min;

    cmp = c;

    t * now = new t;

       now = root;

    while(*cmp)
    {
      min = 1000000;

       now = now->next[*cmp - 'a'];

      if( !now )
      {
        min = 0;

        break;
      }

      else
      {
        if( now->num < min )

        min = now->num;
      }

      cmp ++;

    }

    printf("%d\n" , min);

   }

  return 23;

}

posted on 2009-04-18 14:26 此最相思 阅读(105) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理