算法模板——Trie树

浏览数：23 / 时间：2015年06月08日

实现功能——实现对于不同字符串以及之前出现过的字符串的识别，对于单个长度为L的字符串，复杂度为O(L);

代码不难懂，直接上（在识别字符串方面，个人觉得其好处远远大于hash识别——1.理论上都是O(L) 2.哈希弄不好撞车撞一大串，尤其是哈希策略不太好的时候，而这个绝对不可能撞，严格的O(L) 3.这个代码真心短，一点也不比hash长，只要你链表还会用）

 1 type
 2     pp=^nod;
 3     nod=record
 4               ex:longint;
 5               next:array[char] of pp;
 6     end;
 7 var
 8    i,j,k,l,m,n,ttx:longint;
 9    head,p,p1,p2:pp;
10    s1:ansistring;
11 function getpoint:pp;inline;
12          var p:pp;c1:char;
13          begin
14               new(p);p^.ex:=0;
15               for c1:=chr(0) to chr(255) do p^.next[c1]:=nil;
16               exit(p);
17          end;
18 function getnum(s1:ansistring):longint;
19          var
20             p:pp;i:longint;
21          begin
22               p:=head;
23               for i:=1 to length(s1) do
24                   begin
25                        if p^.next[s1[i]]=nil then p^.next[s1[i]]:=getpoint;
26                        p:=p^.next[s1[i]];
27                   end;
28               if p^.ex=0 then
29                  begin
30                       inc(ttx);
31                       p^.ex:=ttx;
32                  end;
33               exit(p^.ex);
34          end;
35 begin
36      readln(n);
37      head:=getpoint;ttx:=0;
38      for i:=1 to n do
39          begin
40               readln(s1);
41               writeln(GETNum(s1));
42          end;
43      readln;
44 end.
45