轉載自http://epic.32o.cn/article.asp?id=47

今天在vijos有人問我trie樹怎么弄。索性就寫詳細點，讓眾多新手參考一下。
Trie樹就是字符樹，其核心思想就是空間換時間。
舉個簡單的例子。
給你100000個長度不超過10的單詞。對于每一個單詞，我們要判斷他出沒出現過，如果出現了，第一次出現第幾個位置。
這題當然可以用hash來，但是我要介紹的是trie樹。在某些方面它的用途更大。比如說對于某一個單詞，我要詢問它的前綴是否出現過。這樣hash就不好搞了，而用trie還是很簡單。
現在回到例子中，如果我們用最傻的方法，對于每一個單詞，我們都要去查找它前面的單詞中是否有它。那么這個算法的復雜度就是O(n^2)。顯然對于100000的范圍難以接受。現在我們換個思路想。假設我要查詢的單詞是abcd，那么在他前面的單詞中，以b，c，d，f之類開頭的我顯然不必考慮。而只要找以a開頭的中是否存在abcd就可以了。同樣的，在以a開頭中的單詞中，我們只要考慮以b作為第二個字母的……這樣一個樹的模型就漸漸清晰了……
假設有b，abc，abd，bcd，abcd，efg，hii這6個單詞，我們構建的樹就是這樣的。

對于每一個節點，從根遍歷到他的過程就是一個單詞，如果這個節點被標記為紅色，就表示這個單詞存在，否則不存在。
那么，對于一個單詞，我只要順著他從跟走到對應的節點，再看這個節點是否被標記為紅色就可以知道它是否出現過了。把這個節點標記為紅色，就相當于插入了這個單詞。
這樣一來我們詢問和插入可以一起完成，所用時間僅僅為單詞長度，在這一個樣例，便是10。
我們可以看到，trie樹每一層的節點數是26^i級別的。所以為了節省空間。我們用動態鏈表，或者用數組來模擬動態。空間的花費，不會超過單詞數×單詞長度。
程序非常好實現，區區幾行，我就不寫了，自己琢磨吧。
如果還是不懂請留言。

下面提供一個查找單詞是否在給定的字典中的標程：
program trie;
type
    rec=record
    Got:boolean;
    next:array['a'..'z'] of Longint;
    end;
var
   n,i,j,Now,Tn:Longint;
   s:string;
   T:array[1..1000] of rec;
   flag:boolean;
begin
     Readln(n);
     Tn:=1;
     T[1].Got:=False;
     fillchar(T[1].next,sizeof(T[1].next),0);
     for i:=1 to n do
     begin
         readln(s);
         Now:=1;
          for j:=1 to length(s) do
          if T[now].Next[s[j]]<>0 then now:=t[now].next[s[j]] else
         begin
              Inc(Tn);
              T[tn].Got:=false;
              fillchar(T[tn].next,sizeof(T[tn].next),0);
              T[Now].next[s[j]]:=Tn;
              Now:=Tn;
         end;
         T[now].Got:=true;
     end;
     readln(s);
     while s<>'exit' do
     begin
          Now:=1;flag:=true;
          for j:=1 to length(s) do
          if T[now].Next[s[j]]<>0 then now:=t[now].next[s[j]] else
          begin
                flag:=false;
                break;
          end;
          if flag then
               if T[now].Got=false then flag:=false;
          if flag then writeln('the word is in the tree') else
          writeln('can''t find it!');
          Readln(s);
     end;
end.

一個單詞前綴樹的題，但是我卻用trie樹+bm算法簡化版做的

密碼破譯
【問題描述】
由于最近功課過于繁忙，Tim竟然忘記了自己電腦的密碼，幸運的是Tim在設計電腦密碼的時候，用了一個非常特殊的方法記錄下了密碼。這個方法是：Tim把密碼和其它的一些假密碼共同記錄在了一個本子上面。為了能夠從這些字符串中找出正確的密碼，Tim又在另外一個本子上面寫了一個很長的字符串，而正確的密碼就是在這個字符串中出現次數最多的一個密碼。例如串ababa，假若密碼是abab和aba，那么正確的密碼是aba，因為aba在這個字符串中出現了2次。
現在你得到了Tim的這兩個本子，希望你能夠編寫一個程序幫助Tim找出正確的密碼。
【輸入】
輸入由兩個部分組成。其中第一部分由若干行組成，每一行記錄了一個密碼，密碼的均長度小于等于255位，并且都由小寫字母組成。然后一個空行，第二部分記錄了一個很長的字符串，并且以’.’結束，其中只包含了小寫字母。

【輸出】
輸出文件名為Pass.out。輸出文件由僅有一行，為一個整數，表示正確密碼在字符串中出現的次數。如果這個出現次數為0，輸出“No find”。

【樣例】：
Pass.in                                        Pass.out
ab                                            6
abc
bdc
abcd

abcabcabcdbdabcbabdbcabdbdbdbd.

program pass;
const
     filein='pass.in';
     fileout='pass.out';
type
    rec=record
    which:Longint;
    Next:array['a'..'z'] of Longint;
    end;
var
   o,now,i,Tn,Dn,temp,Ans:Longint;
   s:string;
   c:char;
   T:array[1..1000000] of REc;
   data:array[1..5000] of string;
   dLong:array[1..5000] of longint;
   use:array[1..5000] of boolean;
   d:array[1..3000000] of char;
   Appear:array['a'..'z'] of Longint;
   Long:Longint;
   f:boolean;
function Compare(x:Longint):Longint;
var
   s,i,Now,L,temp:Longint;
begin
     s:=0;
     fillchar(appear,sizeof(appear),0);
     L:=length(data[x]);
     for i:=1 to L do
     Appear[data[x][i]]:=i;
     Now:=L;
     while NOw<=Long do
     begin
          if D[now]<>data[x][L] then Inc(now,L-Appear[D[now]]) else
          begin
               temp:=L-1;
               while (temp>0) and (Data[x][temp]=d[Now-(L-temp)]) do dec(temp);
               if temp=0 then Inc(s);
               Inc(Now);
          end;
     end;
     Compare:=S;
end;
procedure sort(l,r:Longint);
var
   i,j,x:Longint;
   sy:string;
   ly:Longint;
begin
     i:=l;j:=r;x:=dLong[(l+r) div 2];
     repeat
           while dLong[i]<x do inc(i);
           while dlong[j]>x do dec(j);
           if i<=j then
           begin
                sy:=data[i];
                data[i]:=data[j];
                data[j]:=sy;
                ly:=dlong[i];
                dlong[i]:=dlong[j];
                dlong[j]:=ly;
                inc(i);
                dec(j);
           end;
     until i>j;
     if i<r then sort(i,r);
     if j>l then sort(l,j);
end;
begin
     fillchar(use,sizeof(use),true);
     fillchar(t,sizeof(t),0);
     Assign(input,filein);
     Assign(output,fileout);
     rewrite(output);
     reset(input);
     tn:=1;
     readln(s);
     Dn:=0;
     while s<>'' do
     begin
          Inc(dn);
          data[dn]:=s;
          dLong[dn]:=length(s);
          readln(s);
     end;
     sort(1,Dn);
     for o:=1 to Dn do
     begin
          s:=data[o];
          NOw:=1;
          f:=true;
          for i:=1 to Length(s) do
          if t[now].Next[s[i]]<>0 then
          begin
              Now:=t[now].next[s[i]];
              if t[now].which<>0 then
              begin
                   f:=false;
                   break
              end;
          end else
          begin
               Inc(tn);
               t[now].next[s[i]]:=tn;
               now:=tn;
          end;
          if f then t[now].which:=o;
          if not f then use[o]:=false;
     end;
     Long:=0;
     repeat
           read(c);
           if c<>'.' then
           begin
                Inc(Long);
                d[Long]:=c;
           end;
     until c='.';
     for i:=1 to Dn do
     begin
          if use[i] then
          begin
               temp:=Compare(i);
               if temp>ans then ans:=temp;
          end;
     end;
     if ans=0 then writeln('No find') else
     writeln(Ans);
     close(input);
     close(output);
end.