LCP 如何帮助查找模式的出现次数？

algorithm data-structures java pattern-matching suffix-array

2022-09-01 23:06:49

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

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

虽然使用二进制搜索来查找模式的出现次数是显而易见的，但我无法弄清楚LCP如何帮助查找此处的出现次数。

例如，对于以下各项的后缀数组：banana

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

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

有什么帮助可以弄清楚LCP如何在这里提供帮助吗？

答案 1

我不知道使用LCP数组而不是执行二进制搜索的任何方法，但我相信您指的是Udi Manber和Gene Myers在后缀数组中描述的技术：一种在线字符串搜索的新方法。

（注：以下解释已于2014年4月9日复制到维基百科文章中，请参阅diff。如果你看看这里和维基百科上的修订历史，你会发现这里的修订历史是先写的。请不要在我的答案中插入“取自维基百科”之类的评论。

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

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

使用标准二进制搜索（没有LCP信息）的问题在于，在您需要进行的每个O（log N）比较中，您将P与后缀数组的当前条目进行比较，这意味着最多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' 的第（k+1）个字符与 M 的字符相同，并且由于 P 在字典上大于 M，因此它在字典上也必须大于 M'。因此，我们继续在右半部分（M',...,R）。
- 情况2：k>lcp（M，M'），即P与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）。

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

总结一下：

可以从LCP计算O（N）时间和O（2 * N）= O（N）空间的LCP-LR
在二进制搜索期间使用 LCP-LR 有助于加快从 O（M*log N）到 O（M+log N）的搜索过程
正如您所建议的那样，您可以使用两个二进制搜索来确定 P 的匹配范围的左端和右端，并且匹配范围的长度与 P 的出现次数相对应。

答案 2

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