POJ2001 - 字典树(trie)的模板题

一口气看了3集《Lady~》终于把拖了半年的烂尾楼给完工了~~一看3:40了...再一想~~擦~~今天整了一天的题还没整出来~~好吧~~AC了....写完睡..

搞Trie是因为看了Mtrix67关于矩阵乘法的日志中提到的AC自动机...AC自动机又必须熟悉Trie和KMP...KMP没啥问题..Trie没接触过..就所幸熟悉了下...

其实这个字典树也很简单...结构上来说是棵树...除了根节点..树上的每个点都代表着一个字母...从第二层出发(根节点不存数据)..每条由叶子节点路径上的点依次组成的字符串即为一个相当于字典里的单词(但不一定所有的单词都是第二层走到叶子,如果字典中的有包含关系...则可能从第二层到中间某点代表一个单词)...Trie里每个节点以及其孩子代表单词表里有当前位置是这个节点的字母下个位置是其孩子的字母的单词.....如用 akb ab abc air oricon orish 所构造出来的字典树为:

我觉得字典树关键的不是树的理解和树的意义....关键是如何来建树..首先是每个节点的定义

struct node
{
    node *a[27];    
    int p;  
}

树上的每个点这样定义...因为每个点后面最多可能跟26个字母~~所以开个27厂的指针..这里用指针是因为这个建树每个点下到底会接上多少个是不清楚的而且差距比较大...而用动态来管理显然很节约空间也方便操作....这里的p是关于这道题而设置的..

建树过程...其实每个点先给26个指针就是判断很方便...如果下一个点前面已经开辟过了...就递归进去...如果没有~~那就开辟新点~~

void make(int k,node *h)
{
    h->p++; 
    if (k>l) return;
    if (h->a[s[n][k]-'a']!=NULL) make(k+1,h->a[s[n][k]-'a']);
    else
    { 
        int i,j; 
        for (i=k;i<=l;i++)
        {
            t=new node;
            t->p=1;
            for (j=0;j<26;j++) t->a[j]=NULL;
            h->a[s[n][i]-'a']=t;
            h=t; 
        }
    } 
    return;
}

回到这道题..是求要用最短的字符来代表字典中的单词.....这里解释用p的意思....我这里的每个点的p代表在建树时有多少个单词经过了这个点....那么再输出时...如果只有一个单词经过这个点..显然从第二层到这个点已经足够表示其单词了...但也要注意..或许一个单词走完了...所有点都是p>1的..那就只能用这个单词的全部来代表它~

Program:

#include<iostream>
using namespace std;
struct node
{
    node *a[27];    
    int p;  
}*t,*h;
char s[1011][35];
int n,i,j,l;
void make(int k,node *h)
{
    h->p++; 
    if (k>l) return;
    if (h->a[s[n][k]-'a']!=NULL) make(k+1,h->a[s[n][k]-'a']);
    else
    { 
        int i,j; 
        for (i=k;i<=l;i++)
        {
            t=new node;
            t->p=1;
            for (j=0;j<26;j++) t->a[j]=NULL;
            h->a[s[n][i]-'a']=t;
            h=t; 
        }
    } 
    return;
}
void find(int k,int m,node *h)
{ 
     printf("%c",s[m][k]);
     if (k==strlen(s[m])-1 || h->p==1) return; 
     find(k+1,m,h->a[s[m][k+1]-'a']);
}
int main()
{ 
    n=0;  h=new node;  h->p=0;
    for (i=0;i<26;i++) h->a[i]=NULL;
    while (~scanf("%s",s[++n]))
    {
         l=strlen(s[n])-1; 
         make(0,h);
    }
    n--;
    for (i=1;i<=n;i++)
    {
         printf("%s ",s[i]);
         find(0,i,h->a[s[i][0]-'a']);
         if (i!=n) printf("\n");
    } 
    return 0;  
}