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   博问   Chat2DB   管理