知识卡片

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

相邻文本后缀公共前缀至多减一

理解等级:高级

后缀数组把T的各后缀按字典序排列,LCP[r]记录第r个后缀与其排序前驱的最长公共前缀长度。若T[i−1:]与其排序前驱共有ℓ>1个字符,同时删去两个后缀的首字符,就得到T[i:]与另一个更小后缀至少共有ℓ−1个字符。

这个“另一个后缀”未必紧挨T[i:];但字典序中夹在两个具有同一长度ℓ−1前缀的字符串之间的后缀,也必须具有该前缀。因此T[i:]与它自己的排序前驱的LCP至少为ℓ−1。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第32章 字符串匹配 · 查看原书依据

      Lemma 32.8 Consider suffixes T[i – 1:] and T[i:], which appear at positions rank[i – 1] and rank[i], respectively, in the lexicographically sorted order of suffixes. If LCP[rank[i – 1]] = l > 1, then the suffix T[i:], which is T[i – 1:] with its first character removed, has LCP[rank[i]] ≥ l – 1.

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[75000,80000))。 - 结论依据:原文第32.5节复杂度、LCP算法与引理,或章末问题32-1/32-2给出的定义与构造步骤。 - 原始内容:Lemma 32.8 Consider suffixes T [ i – 1:] and T [ i :], which appear at positions rank [ i – 1] and rank [ i ], respectively, in the lexicographically sorted order of suffixes. If LCP [ rank [ i – 1]] = l > 1, then the suffix T [ i :], which is T [ i – 1:] with its first character removed, has LCP [ rank [ i ]] ≥ l – 1.