如何LCP在寻找一种模式的出现的次数帮助吗？(How does LCP help in findin

我已阅读， 最长公共前缀（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阵列，而不是执行二进制搜索的任何方式，但我相信你是指什么是迪·曼伯和基因迈尔斯中描述的技术后缀芯片：一个上线的字符串搜索的新方法。

我们的想法是这样的：为了找到在文本T（长度N）给定的字符串P（长度M）的发生次数，

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

使用标准的二进制搜索（不 LCP信息）的问题是，在每一个的O（日志N）你需要做比较，你比较P到后缀数组的当前条目，这意味着一个完整的字符串比较到m个字符。所以复杂度为O（M * log n）的。

在LCP-LR阵列有助于改善这对O（M +日志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。现在有三种可能性：
- 情况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相同。要决定是否继续在左边或右边的一半，它足以为P比较M” 开始从（K + 1）个字符 。
我们递归继续。

总的效果是， 没有P的性质是相对于文本的任何字符超过一次 。字符比较的总数为m为界，所以总的复杂性是确实O（M +日志N）。

显然，关键剩下的问题是我们是如何预先计算LCP-LR所以它能够告诉我们在O（1）时间后缀阵列中的任何两个条目之间的LCP？至于你说，标准的LCP阵列告诉您对于任意的x 连续的条目只，即LCP（X-1，X）的LCP。但是，上述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的值 - 我建议发布一个单独的问题，如果你需要的是一个详细的说明。

总结一下：