知识卡片

普通读书笔记卡 · 3707.a.1

最大公共前缀定位最长重复片段

理解等级:中级

LCP的最大值给出文本中最长重复子串的长度;在达到最大值的相邻后缀上取同长前缀,就是一个实例。因为任意重复片段都对应至少两个后缀,其共同前缀会在排序后的相邻位置体现。

这张卡片看不懂?

已有反馈 · 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