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

Question

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

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

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

例如,对于此后缀数组banana:

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

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

有什么帮助搞清楚LCP如何帮助吗？

Answer 1

我不知道如何使用LCP阵列而不是执行二进制搜索,但我相信你所指的是Udi Manber和Gene Myers在Suffix数组中描述的技术:一种用于在线字符串搜索的新方法.

这个想法是这样的:为了找到文本T(长度N)中给定字符串P(长度m)的出现次数,

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

使用标准的二进制搜索(这个问题不 LCP的信息)的是,在每一个的O(日志N)的比较,你需要,你比较P到后缀数组的当前条目,这意味着一个完整的字符串比较的了到m个字符.因此复杂度为O(m*log N).

LCP-LR阵列通过以下方式帮助将其提高到O(m + log N):

• 在二进制搜索算法期间的任何时候,您都会像往常一样考虑后缀数组的范围(L,...,R)及其中心点M,并决定是否继续在左子范围内搜索( L,...,M)或在右子范围(M,...,R).
• 为了做出决定,你比较p来在M.字符串如果P是相同的男,你都做了,但如果没有,你会比P的前k个字符,然后决定P是否是字典序小于或大于M.让我们假设结果是P大于M.

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

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

  现在的诀窍是LCP-LR被预先计算,使得O(1)-lookup告诉你M和M',lcp(M,M')的最长公共前缀.

  您已经知道(从上一步开始)M本身具有与P:lcp(P,M)= k共同的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).

此外,还有一个直接的递归算法来计算从标准的LCP阵列O(N)时间LCP-LR的2级*N的值 - 我建议发布一个单独的问题,如果你需要的是一个详细的说明.

总结一下:

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