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

Question

我已经读过，最长的公共前缀(LCP)可以用来查找字符串中模式出现的次数。

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

虽然使用二进制搜索来查找模式出现的次数是显而易见的，但我不知道LCP如何在这里帮助查找出现的次数。

例如，对于banana的这个后缀数组

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

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

有什么帮助找出LCP在这里有什么帮助吗？

Answer 1

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

(注:以下解释已复制到2014年4月9日维基百科的一篇文章中，见比较。如果你看看这里和维基百科的修订历史，你会发现这里的修改是首先写的。请不要在我的回答中插入“摘自维基百科”之类的评论。)

其思想是:为了在文本T(长度N)中找到给定字符串P(长度m)的出现数，

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

使用标准二进制搜索(没有LCP信息)的问题是，在中，您需要进行的每一个O(log )比较都会将P与后缀数组的当前条目进行比较，这意味着最多为m个字符的全字符串比较。其复杂度为O(m*log )。

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

• 在二进制搜索算法中的任何一点上，您都会像往常一样考虑后缀数组及其中心点M的范围(L，.，R)，并决定是在左子范围(L，.，M)还是在右子范围(M，.，R)继续搜索。
• 为了做出决定，你把P和M处的字符串进行比较，如果P和M相同，你就完成了，但如果不是，你会比较P的前k个字符，然后决定P在词汇上是小于还是大于M，假设结果是P大于M。
• 因此，在下一步中，考虑(M，.，R)和中间的一个新的中心点M‘： M.我.我们知道: lcp(P，M)==k 技巧现在是预先计算LCP-LR，使得O(1)-lookup告诉您最长的公共前缀M和M'，lcp(M，M')。 您已经知道(从上一步开始)，M本身有一个前缀为k个字符，与P: lcp(P，M)=k有共同之处。

- Case 1: k < lcp(M,M'), i.e. P has _fewer_ prefix characters in common with M than M has in common with M'. This means the (k+1)-th character of M' is the same as that of M, and since P is lexicographically larger than M, it must be lexicographically larger than M', too. So we continue in the right half (M',...,R).
- Case 2: k > lcp(M,M'), i.e. P has _more_ prefix characters in common with M than M has in common with M'. Consequently, if we were to compare P to M', the common prefix would be smaller than k, and M' would be lexicographically larger than P, so, _without actually making the comparison_, we continue in the left half (M,...,M').
- Case 3: k == lcp(M,M'). So M and M' are both identical with P in the first k characters. To decide whether we continue in the left or right half, it suffices to compare P to M' **starting from the (k+1)-th character**.

​

• 我们继续递归地进行。

总体效果是，没有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)，对这些可能的范围预先计算lcp(L，M)和lcp(M，R)就足够了.这是2*N不同的预先计算值，因此LCP-LR在大小上是O(N) .

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

总结：

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

Answer 2

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