當前位置:成語大全網 - 英語詞典 - Trie單詞查找樹 pascal 實現

Trie單詞查找樹 pascal 實現

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.