算法模板——Trie树
实现功能——实现对于不同字符串以及之前出现过的字符串的识别，对于单个长度为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 本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-01-21 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读