轉(zhuǎn)載自
http://epic.32o.cn/article.asp?id=47今天在vijos有人問(wèn)我trie樹(shù)怎么弄。索性就寫(xiě)詳細(xì)點(diǎn)，讓眾多新手參考一下。
Trie樹(shù)就是字符樹(shù)，其核心思想就是空間換時(shí)間。
舉個(gè)簡(jiǎn)單的例子。
給你100000個(gè)長(zhǎng)度不超過(guò)10的單詞。對(duì)于每一個(gè)單詞，我們要判斷他出沒(méi)出現(xiàn)過(guò)，如果出現(xiàn)了，第一次出現(xiàn)第幾個(gè)位置。
這題當(dāng)然可以用hash來(lái)，但是我要介紹的是trie樹(shù)。在某些方面它的用途更大。比如說(shuō)對(duì)于某一個(gè)單詞，我要詢問(wèn)它的前綴是否出現(xiàn)過(guò)。這樣hash就不好搞了，而用trie還是很簡(jiǎn)單。
現(xiàn)在回到例子中，如果我們用最傻的方法，對(duì)于每一個(gè)單詞，我們都要去查找它前面的單詞中是否有它。那么這個(gè)算法的復(fù)雜度就是O(n^2)。顯然對(duì)于100000的范圍難以接受。現(xiàn)在我們換個(gè)思路想。假設(shè)我要查詢的單詞是abcd，那么在他前面的單詞中，以b，c，d，f之類開(kāi)頭的我顯然不必考慮。而只要找以a開(kāi)頭的中是否存在abcd就可以了。同樣的，在以a開(kāi)頭中的單詞中，我們只要考慮以b作為第二個(gè)字母的……這樣一個(gè)樹(shù)的模型就漸漸清晰了……
假設(shè)有b，abc，abd，bcd，abcd，efg，hii這6個(gè)單詞，我們構(gòu)建的樹(shù)就是這樣的。
對(duì)于每一個(gè)節(jié)點(diǎn)，從根遍歷到他的過(guò)程就是一個(gè)單詞，如果這個(gè)節(jié)點(diǎn)被標(biāo)記為紅色，就表示這個(gè)單詞存在，否則不存在。
那么，對(duì)于一個(gè)單詞，我只要順著他從跟走到對(duì)應(yīng)的節(jié)點(diǎn)，再看這個(gè)節(jié)點(diǎn)是否被標(biāo)記為紅色就可以知道它是否出現(xiàn)過(guò)了。把這個(gè)節(jié)點(diǎn)標(biāo)記為紅色，就相當(dāng)于插入了這個(gè)單詞。
這樣一來(lái)我們?cè)儐?wèn)和插入可以一起完成，所用時(shí)間僅僅為單詞長(zhǎng)度，在這一個(gè)樣例，便是10。
我們可以看到，trie樹(shù)每一層的節(jié)點(diǎn)數(shù)是26^i級(jí)別的。所以為了節(jié)省空間。我們用動(dòng)態(tài)鏈表，或者用數(shù)組來(lái)模擬動(dòng)態(tài)。空間的花費(fèi)，不會(huì)超過(guò)單詞數(shù)×單詞長(zhǎng)度。
程序非常好實(shí)現(xiàn)，區(qū)區(qū)幾行，我就不寫(xiě)了，自己琢磨吧。
如果還是不懂請(qǐng)留言。
下面提供一個(gè)查找單詞是否在給定的字典中的標(biāo)程：
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.
一個(gè)單詞前綴樹(shù)的題，但是我卻用trie樹(shù)+bm算法簡(jiǎn)化版做的
密碼破譯
【問(wèn)題描述】
由于最近功課過(guò)于繁忙，Tim竟然忘記了自己電腦的密碼，幸運(yùn)的是Tim在設(shè)計(jì)電腦密碼的時(shí)候，用了一個(gè)非常特殊的方法記錄下了密碼。這個(gè)方法是：Tim把密碼和其它的一些假密碼共同記錄在了一個(gè)本子上面。為了能夠從這些字符串中找出正確的密碼，Tim又在另外一個(gè)本子上面寫(xiě)了一個(gè)很長(zhǎng)的字符串，而正確的密碼就是在這個(gè)字符串中出現(xiàn)次數(shù)最多的一個(gè)密碼。例如串a(chǎn)baba，假若密碼是abab和aba，那么正確的密碼是aba，因?yàn)閍ba在這個(gè)字符串中出現(xiàn)了2次。
現(xiàn)在你得到了Tim的這兩個(gè)本子，希望你能夠編寫(xiě)一個(gè)程序幫助Tim找出正確的密碼。
【輸入】
輸入由兩個(gè)部分組成。其中第一部分由若干行組成，每一行記錄了一個(gè)密碼，密碼的均長(zhǎng)度小于等于255位，并且都由小寫(xiě)字母組成。然后一個(gè)空行，第二部分記錄了一個(gè)很長(zhǎng)的字符串，并且以’.’結(jié)束，其中只包含了小寫(xiě)字母。
【輸出】
輸出文件名為Pass.out。輸出文件由僅有一行，為一個(gè)整數(shù)，表示正確密碼在字符串中出現(xiàn)的次數(shù)。如果這個(gè)出現(xiàn)次數(shù)為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.