POJ 2001 Shortest Prefixes(字典树）-白红宇

POJ 2001 Shortest Prefixes(字典树）

阅读量：5044 次

发布时间：2019-06-12

本文共 962 字，大约阅读时间需要 3 分钟。

题目地址：

考察的字典树，利用的是建树时将每个点仅仅要走过就累加。最后从根节点開始遍历，当遍历到仅仅有1次走过的时候，就说明这个地方是最短的独立前缀。然后记录下长度，输出就可以。

代码例如以下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include
             
              using namespace std;char s[1100][30];struct node{ int flag; node *next[30];};node *newnode(){ int i; node *p; p=new node; for(i=0;i<26;i++) { p->next[i]=NULL; } p->flag=0; return p;}void insert1(node *root, char *s){ int i, len=strlen(s), x; node *p=root; for(i=0;i
              
               next[x]==NULL) p->next[x]=newnode(); p=p->next[x]; p->flag++; }}int seach(node *root, char *s){ int i, len=strlen(s), x, pos=len; node *p=root; for(i=0;i
               
                next[x]; if(p->flag==1) { pos=i+1; break; } } return pos;}int main(){ node *root; root =newnode(); int cnt=0, i, j, k; while(scanf("%s",s[cnt])!=EOF) { insert1(root,s[cnt]); cnt++; } for(i=0;i

转载于:https://www.cnblogs.com/zfyouxi/p/4005670.html

你可能感兴趣的文章