[PKU 3630] 字符串(二) {Trie 字典树}

时间:2022-12-30 13:26:34

{

开始讨论字符串的问题

上一篇是转载Matrix67的KMP算法讲解

这一篇主要讨论Trie

}

 

Trie (发音Try)

是一棵用于存储多个字符串的多叉树

由于插入和查询都极为高效 又称字典树

树的叉数就是字符串所含的字母种数

大写字母字典树就是一棵26叉树

我们以这种Trie为例 以方便讨论

[PKU 3630] 字符串(二) {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插入的代码

[PKU 3630] 字符串(二) {Trie 字典树}[PKU 3630] 字符串(二) {Trie 字典树}Trie_Build
   
   
   
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代码就可以解决了

直接帖贴代码

[PKU 3630] 字符串(二) {Trie 字典树}[PKU 3630] 字符串(二) {Trie 字典树}Phone
   
   
   
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/