知识卡片
相邻文本后缀公共前缀至多减一
后缀数组把T的各后缀按字典序排列,LCP[r]记录第r个后缀与其排序前驱的最长公共前缀长度。若T[i−1:]与其排序前驱共有ℓ>1个字符,同时删去两个后缀的首字符,就得到T[i:]与另一个更小后缀至少共有ℓ−1个字符。
这个“另一个后缀”未必紧挨T[i:];但字典序中夹在两个具有同一长度ℓ−1前缀的字符串之间的后缀,也必须具有该前缀。因此T[i:]与它自己的排序前驱的LCP至少为ℓ−1。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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.