知识卡片
计算LCP复用前一文本后缀匹配
按文本起点i递增计算LCP:用rank找到T[i:]的排序前驱,从上轮公共前缀长度减一开始,只比较后续字符。
引理保证这个起点不超过真实LCP;比较结束后写入LCP[rank[i]]。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第32章 字符串匹配 · 查看原书依据
Upon considering a suffix T[i:], line 8 determines the suffix T[j:] that immediately precedes T[i:] in the lexicographically sorted order. At this point, the longest common prefix of T[j:] and T[i:] has length at least l. This property certainly holds upon the first iteration of the for loop, when l = 0. Assuming that line 12 sets LCP[rank[i]] correctly, line 14 (which decrements l if it is positive) and Lemma 32.8 maintain this property for the next iteration. The longest common prefix of T[j:] and T[i:] might be even longer than the value of l at the start of the iteration, however. Lines 9–11 increment l for each additional character the prefixes have in common so that it achieves the length of the longest common prefix.