我参考了下面的一篇文档。
http://linux.thai.net/~thep/datrie/datrie.html文档描述的很详细,我的疑问是,base,check,next这几个数组里面存放的元素都是什么?实现的核心内容是状态转移,这是我的理解。另外,为什么第二种实现可以省掉next数组呢?
http://linux.thai.net/~thep/datrie/datrie.html文档描述的很详细,我的疑问是,base,check,next这几个数组里面存放的元素都是什么?实现的核心内容是状态转移,这是我的理解。另外,为什么第二种实现可以省掉next数组呢?
解决方案 »
- 指针问题。
- VC6添加文件崩溃
- 菜单句柄是否也是窗口句柄,能否给他发消息
- 请问客户端给服务器每次发信息都一定要用Connect重新连一次吗?不可以只连接一次做个全局变量吗?
- 内存泄漏的问题
- CTime 如何转化为 DWORD?
- 高分求~!哪有多线程写文件的方法,像写IIS日志文件一样。同一时间有多个线程来向文件里写数据(一行)
- 我用ENUM可以找到所有能在"网上邻居"显示的计算机,但是怎么样能能把所有能PING到的机子都找出来呢?
- 各位:请问我怎么做一个在对话框里,单击右键时出现一个自己定义的菜单呀,求救呀,UP有分!
- 用VC编程应知道多少C++函数?你们都常用的有哪些?
- 包含"afx.h"的问题
- window 7 sdk有什么用我装了vs2010旗舰版还用装它吗?
{ Move base for state s to a new place beginning at b }
begin
foreach input character c for the state s
{ i.e. foreach c such that check[base[s] + c]] = s }
begin
check[b + c] := s; { owner }
base[b + c] := base[base[s] + c]; { copy data }
{ the node base[s] + c is to be moved to b + c;
Hence, for any i for which check[i] = base[s] + c, update check[i] to b + c }
foreach input character d for the node base[s] + c
begin
check[base[base[s] + c] + d] := b + c
end;
check[base[s] + c] := none { free the cell }
end;
base[s] := b
end
后面的我再回去研究看看。ConstructionThe construction of double-array trie is in principle the same as that of tripple-array trie. The difference is the base relocation:Procedure Relocate(s : state; b : base_index)
{ Move base for state s to a new place beginning at b }
begin
foreach input character c for the state s
{ i.e. foreach c such that check[base[s] + c]] = s }
begin
check[b + c] := s; { owner }
base[b + c] := base[base[s] + c]; { copy data }
{ the node base[s] + c is to be moved to b + c;
Hence, for any i for which check[i] = base[s] + c, update check[i] to b + c }
foreach input character d for the node base[s] + c
begin
check[base[base[s] + c] + d] := b + c
end;
check[base[s] + c] := none { free the cell }
end;
base[s] := b
end
http://linux.thai.net/~thep/datrie/doubreloc.gif
ConstructionThe construction of double-array trie is in principle the same as that of tripple-array trie. The difference is the base relocation:Procedure Relocate(s : state; b : base_index)
{ Move base for state s to a new place beginning at b }
begin
foreach input character c for the state s
{ i.e. foreach c such that check[base[s] + c]] = s }
begin
check[b + c] := s; { owner }
base[b + c] := base[base[s] + c]; { copy data }
{ the node base[s] + c is to be moved to b + c;
Hence, for any i for which check[i] = base[s] + c, update check[i] to b + c }
foreach input character d for the node base[s] + c
begin
check[base[base[s] + c] + d] := b + c
end;
check[base[s] + c] := none { free the cell }
end;
base[s] := b
end