{
开始讨论字符串的问题
上一篇是转载Matrix67的KMP算法讲解
这一篇主要讨论Trie
}
Trie (发音Try)
是一棵用于存储多个字符串的多叉树
由于插入和查询都极为高效 又称字典树
树的叉数就是字符串所含的字母种数
大写字母字典树就是一棵26叉树
我们以这种Trie为例 以方便讨论
比如要存储6个串{SHE SHR SAY HE HR HER}
Trie就是如上图所示的一棵多叉树
一.Trie的结构
基本的Trie的一个节点 包含这么两个信息
Son['A'..'Z']:Pointer {儿子指针数组 下标是字符集合}
Tail:Boolean {该节点是否是一个单词的结尾}
Trie的字符信息纪录在边(指针)上 节点保存一些附加信息
一般Trie的空间占用比较大 与字符总数成正比
(鉴于Pascal的指针很鸡肋 下文一般用数组模拟指针)
二.Trie的插入(建树)
总结起来就是边读边走边插入
首先让当前指针P指向Root (预处理时注意新建Root)
接下来每读入一个字符判断当前节点是否有这样一个儿子
如果没有实时新建 判断完后然后继续往这个儿子走 即P=Son[Ch]
读完一个串 最后一个节点的Tail记为True 表示是词尾
给出Trie插入的代码
newnode(root);
readln(n);
for i: = 1 to n do
begin
p: = root;
while not eoln do
begin
read(ch);
c: = ord(ch) - 96 ;
if s[p][c] = 0
then newnode(s[p][c]);
p: = s[p][c];
end ;
inc(g[p]);
readln;
end ;
三.Trie的查询
查询就是边读边走 不插入
每读入一个字符 判断有没有所需的儿子 没有就代表查询失败
如果读到完 最后的节点不是词尾(根据Tail判断) 也是查询失败
代码和查询类似
四.总结
Trie的插入和查询时间复杂度都是线性的 O(Length)
但是空间复杂度达到了 O(K*Length) 或 O(∑Length)
针对这个问题 可以采取压缩Trie来解决 使空间复杂度达到 O(K)
这个方法我还不会 也没有碰到要用的地方
Lazy-Tag之~
最后给出一个用来测试Trie的问题
http://poj.org/problem?id=3630
最简单Trie代码就可以解决了
直接帖贴代码
const maxc = 10 ;
maxn = 500000 ;
var t: array [ 1 ..maxn] of longint;
n: array [ 1 ..maxn, 1 ..maxc] of longint;
tt,ca,m,i,p,k,root:longint;
flag,bool:boolean;
ch:char;
procedure NewNode( var x:longint);
var i:longint;
begin
inc(tt); x: = tt;
t[x]: = 0 ;
for i: = 1 to maxc do
n[x][i]: = 0 ;
end ;
begin
assign(input, ' PList.in ' ); reset(input);
assign(output, ' PList2.out ' ); rewrite(output);
readln(ca);
while ca > 0 do
begin
tt: = 0 ;
dec(ca);
readln(m);
NewNode(root);
flag: = true;
for i: = 1 to m do
begin
p: = root;
bool: = true;
while not eoln do
begin
read(ch);
k: = ord(ch) - 47 ;
if n[p][k] = 0
then begin
NewNode(n[p][k]);
bool: = false;
end ;
p: = n[p][k];
if t[p] > 0 then flag: = false;
end ;
if bool = true then flag: = false;
inc(t[p]);
readln;
end ;
if flag
then writeln( ' YES ' )
else writeln( ' NO ' );
end ;
close(input); close(output);
end .
讨论过了Trie和KMP 我们就可以考虑一个牛B的东西
——Aho-Corasick自动机了
在第三 第四篇文章里介绍
BOB HAN 原创 转载请注明出处 http://www.cnblogs.com/Booble/