21

我读过最长公共前缀（LCP）可用于查找字符串中模式的出现次数。

具体来说，您只需要创建文本的后缀数组，对其进行排序，然后无需进行二进制搜索来查找范围以便计算出现次数，您只需计算文本中每个连续条目的 LCP后缀数组。

尽管使用二进制搜索来查找模式的出现次数是显而易见的，但我无法弄清楚 LCP 如何帮助在这里找到出现次数。

例如对于这个后缀数组banana：

LCP  Suffix entry
N/A  a  
1    ana  
3    anana  
0    banana  
0    na  
2    nana

LCP 如何帮助找到像“banana”或“na”这样的子字符串的出现次数对我来说并不明显。

任何帮助弄清楚 LCP 如何在这里提供帮助？

4

2 回答 2

33

我不知道使用 LCP 数组而不是执行二进制搜索的任何方法，但我相信您所指的是 Udi Manber 和 Gene Myers 在Suffix arrays: a new method for online string search 中描述的技术。

（注意：以下解释已被复制到 2014 年 4 月 9 日的维基百科文章中，请参阅diff。如果您查看此处和维基百科上的修订历史，您会发现这里的内容是先写的。请不要插入像“取自维基百科”这样的评论进入我的回答。）

这个想法是这样的：为了找到给定字符串 P（长度 m）在文本 T（长度 N）中出现的次数，

  • 您对 T 的后缀数组使用二进制搜索（就像您建议的那样）
  • 但是您可以使用 LCP 数组作为辅助数据结构来加快速度。更具体地说，您生成一个特殊版本的 LCP 阵列（我将在下面将其称为 LCP-LR）并使用它。

使用标准二进制搜索（没有LCP 信息）的问题是，在您需要进行的每个 O(log N) 比较中，您将 P 与后缀数组的当前条目进行比较，这意味着up的完整字符串比较到 m 个字符。所以复杂度是 O(m*log N)。

LCP-LR 阵列通过以下方式帮助将其改进为 O(m+log N)：

  • 在二分搜索算法的任何时候，您都像往常一样考虑后缀数组的范围 (L,...,R) 及其中心点 M，并决定是否继续在左侧子范围 ( L,...,M) 或在正确的子范围内 (M,...,R)。
  • 为了做出决定，您将 P 与 M 处的字符串进行比较。如果 P 与 M 相同，则完成，但如果不是，您将比较 P 的前 k 个字符，然后确定 P 在字典上是否更小大于 M。假设结果是 P 大于 M。

  • 因此，在下一步中，您考虑 (M,...,R) 和中间的新中心点 M'：

                  M ...... M' ...... R
              |
       we know:
          lcp(P,M)==k

    现在的诀窍是 LCP-LR 是预先计算的，因此 O(1) 查找会告诉您 M 和 M' 的最长公共前缀 lcp(M,M')。

    您已经（从上一步中）知道 M 本身具有与 P 相同的 k 个字符的前缀：lcp(P,M)=k。现在有三种可能：

    • 情况 1：k < lcp(M,M')，即 P与 M 的共同前缀字符少于M 与 M' 的共同前缀字符。这意味着 M' 的第 (k+1) 个字符与 M 的字符相同，并且由于 P 在字典上大于 M，因此它也必须在字典上大于 M'。所以我们继续右半部分（M'，...，R）。
    • 情况 2：k > lcp(M,M')，即 P与 M 的共同前缀字符多于M 与 M' 的共同前缀字符。因此，如果我们将 P 与 M' 进行比较，公共前缀将小于 k，并且 M' 在字典序上将大于 P，因此，在不实际进行比较的情况下，我们继续左半部分 (M,.. .,M')。
    • 情况 3：k == lcp(M,M')。所以 M 和 M' 在前 k 个字符中都与 P 相同。要决定我们是继续左半部分还是右半部分，只需从第 (k+1) 个字符开始比较 P 和 M' 就足够了。

  • 我们继续递归。

总体效果是P 的任何字符都不会与文本中的任何字符进行多次比较。字符比较的总数以 m 为界，因此总复杂度确实是 O(m+log N)。

显然，剩下的关键问题是我们如何预先计算 LCP-LR，以便它能够在 O(1) 时间内告诉我们后缀数组的任意两个条目之间的 lcp？正如您所说，标准 LCP 数组仅告诉您连续条目的 lcp ，即任何 x 的 lcp(x-1,x)。但是上面描述的M和M'不一定是连续的条目，那是怎么做的呢？

关键是要意识到在二分查找过程中只会出现特定的范围 (L,...,R)：它总是从 (0,...,N) 开始并在中心除以它，然后继续向左或向右，然后再次划分那一半，依此类推。如果你想一想：后缀数组的每个条目在二分搜索期间恰好作为一个可能范围的中心点出现。因此，恰好有 N 个不同的范围 (L...M...R) 可能在二分搜索期间发挥作用，并且对于那些 N 个可能的情况预先计算 lcp(L,M) 和 lcp(M,R) 就足够了范围。所以这是 2*N 个不同的预计算值，因此 LCP-LR 的大小为 O(N)。

此外，有一个直接的递归算法可以在 O(N) 时间内从标准 LCP 数组计算 LCP-LR 的 2*N 值——如果您需要详细描述，我建议发布一个单独的问题。

总结一下：

  • 可以在 O(N) 时间和 O(2*N)=O(N) 空间从 LCP 计算 LCP-LR
  • 在二分搜索期间使用 LCP-LR 有助于将搜索过程从 O(M*log N) 加速到 O(M+log N)
  • 正如您所建议的，您可以使用两次二进制搜索来确定 P 的匹配范围的左端和右端，并且匹配范围的长度与 P 的出现次数相对应。
于 2012-07-07T11:48:33.173 回答
0

最长公共前缀 (LCP) 是后缀树中的最低公共祖先 (LCA)。一旦你有了最低共同祖先，你就可以计算从 LCA 分支出来的节点的数量。这将为您提供后缀树中模式的出现次数。这就是 LCP 和 LCA 之间的关系。

于 2017-05-03T22:06:34.970 回答