知识卡片
倍增排序维持片段字典序不变式
后缀数组按字典序列出文本T各后缀的起点。倍增算法为每个起点i保存长度ℓ片段T[i:i+ℓ−1]的秩;越过文本末尾的部分用小于正常字符的哨兵秩处理。
初轮由字符编码得到短片段的秩。若长度ℓ片段的秩已正确,长度2ℓ片段可拆成前、后两个长度ℓ片段,因此用秩对(rank[i], rank[i+ℓ])排序,就得到长度2ℓ片段的正确字典序和新秩。ℓ每轮翻倍;当ℓ≥n时,每个片段已覆盖从其起点到文本末尾,按秩排列的起点就是后缀数组。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第32章 字符串匹配 · 查看原书依据
This example illuminates why the COMPUTE-SUFFIX-ARRAY procedure works. The initial ranks established in lines 2–7 are simply the ord values of the characters in the text, and so when line 8 sorts the substr-rank array, its ordering corresponds to the lexicographic ordering of the length-2 substrings. Each iteration of the while loop of lines 10–19 takes sorted substrings of length l and produces sorted substrings of length 2l. Once l reaches or exceeds n, all substrings have been sorted. Within an iteration of the while loop, the MAKE-RANKS procedure “re-ranks” the substrings that were sorted, either by line 8 before the first iteration or by line 18 in the previous iteration. MAKE-RANKS takes a substr-rank array,