知识卡片

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

计算LCP复用前一文本后缀匹配

理解等级:高级

按文本起点i递增计算LCP:用rank找到T[i:]的排序前驱,从上轮公共前缀长度减一开始,只比较后续字符。

引理保证这个起点不超过真实LCP;比较结束后写入LCP[rank[i]]。

这张卡片看不懂?

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

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[80000,85000))。 - 结论依据:原文第32.5节复杂度、LCP算法与引理,或章末问题32-1/32-2给出的定义与构造步骤。 - 原始内容: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.