知识卡片
空后段秩为零使短后缀先行
倍增排序用左右秩比较片段;超过文本末尾的右段视为空串,秩定为0,低于任何非空片段。这样一个后缀恰为另一个的前缀时,较短者仍正确地排在前面。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第32章 字符串匹配 · 查看原书依据
An empty substring always has rank 0, since it is lexicographically less than any nonempty substring. COMPUTE-SUFFIX-ARRAY(T, n) 1 allocate arrays substr-rank[1:n], rank[1:n], and SA[1:n] 2 for i = 1 to n 3 substr-rank[i].left-rank = ord(T[i]) 4 if i < n 5 substr-rank[i].right-rank = ord(T[i + 1]) 6 else substr-rank[i].right-rank = 0 7 substr-rank[i].index = i 8 sort the array substr-rank into monotonically increasing order based on the
参考来源
- 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[65000,70000))。
- 结论依据:原文第32.5节后缀数组、LCP和倍增构造的定义、示例或正确性推导。
- 原始内容:An empty substring always has rank 0, since it is lexicographically less than any nonempty substring. C OMPUTE -S UFFIX -A RRAY ( T , n ) 1 allocate arrays substr-rank [1: n ], rank [1: n ], and SA [1: n ] 2 for i = 1 to n 3 substr-rank [ i ]. left-rank = ord( T [ i ]) 4 if i < n 5 substr-rank [ i ]. right-rank = ord( T [ i + 1]) 6 else substr-rank [ i ]. right-rank = 0 7 substr-rank [ i ]. index = i 8 sort the array substr-rank into monotonically increasing order based on the