知识卡片
最大公共前缀定位最长重复片段
LCP的最大值给出文本中最长重复子串的长度;在达到最大值的相邻后缀上取同长前缀,就是一个实例。因为任意重复片段都对应至少两个后缀,其共同前缀会在排序后的相邻位置体现。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第32章 字符串匹配 · 查看原书依据
With the longest common prefix array, you can find a longest repeated substring, that is, the longest substring that occurs more than once in the text. If LCP[i] contains a maximum value in the LCP array, then a longest repeated substring appears in T[SA[i]:SA[i] + LCP[i] – 1]. In the example of Figure 32.11, the LCP array has one maximum value: LCP[3] = 4. Therefore, since SA[3] = 2, the longest repeated substring is T[2:5] = atat. Exercise 32.5-3 asks you to use the suffix array and longest common
参考来源
- 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[60000,65000))。
- 结论依据:原文第32.5节后缀数组、LCP和倍增构造的定义、示例或正确性推导。
- 原始内容:With the longest common prefix array, you can find a longest repeated substring, that is, the longest substring that occurs more than once in the text. If LCP [ i ] contains a maximum value in the LCP array, then a longest repeated substring appears in T [ SA [ i ]: SA [ i ] + LCP [ i ] – 1]. In the example of Figure 32.11 , the LCP array has one maximum value: LCP [3] = 4. Therefore, since SA [3] = 2, the longest repeated substring is T [2:5] = atat . Exercise 32.5-3 asks you to use the suffix array and longest common