知识卡片
样本后缀递归规模约为三分之二
问题32-2先把样本起点的三字符块编码成秩序列P′。
若秩均不同,直接由首字符秩得到其后缀次序;否则递归排序P′,再映回原文本的样本后缀。
子问题规模约2n/3。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第32章 字符串匹配 · 查看原书依据
Otherwise, recurse to compute the suffix array of P′, treating the ranks in P′ as the input characters in the recursive call. Figure 32.15 shows the suffix array SAP′ for our example. Since the number of metacharacters in P, and hence the length of P′, is approximately 2n/3, this recursive subproblem is smaller than the current problem. F. From SAP′ and the positions in T corresponding to the sample positions, compute the list of positions of the sorted sample suffixes of the original text T. Figure 32.15 shows the list of positions in T of the sorted sample suffixes in our example. 2. The nonsample
参考来源
- 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[90000,95000))。
- 结论依据:原文章末问题32-2给出的构造步骤、问题32-3给出的BWT定义及逆变换说明,或章末脚注。
- 原始内容:Otherwise, recurse to compute the suffix array of P ′, treating the ranks in P ′ as the input characters in the recursive call. Figure 32.15 shows the suffix array SA P ′ for our example. Since the number of metacharacters in P , and hence the length of P ′, is approximately 2 n /3, this recursive subproblem is smaller than the current problem. F. From SA P ′ and the positions in T corresponding to the sample positions, compute the list of positions of the sorted sample suffixes of the original text T . Figure 32.15 shows the list of positions in T of the sorted sample suffixes in our example. 2. The nonsample