LCP如何帮助查找模式的出现次数？
我已经读过最长公共前缀（LCP）可用于查找字符串中模式的出现次数。
具体来说，您只需要创建文本的后缀数组，对其进行排序，然后不进行二进制搜索以找到范围，以便您可以计算出现次数，只需计算每个连续条目的LCP即可。后缀数组。
虽然使用二进制搜索来查找模式的出现次数是显而易见的，但我无法弄清楚LCP如何帮助找到此处出现的次数。
例如，对于banana这个后缀数组：
LCP Suffix entry N/A a 1 ana 3 anana 0 banana 0 na 2 nana
LCP如何帮助找到像“banana”或“na”这样的子字符串的出现次数对我来说并不明显。
有什么帮助搞清楚LCP如何帮助吗？
我不知道如何使用LCParrays而不是进行二进制搜索，但我相信你所指的是Udi Manber和Gene Myers在后缀数组中描述的技术：一种用于在线字符串搜索的新方法 。
这个想法是这样的：为了找到文本T（长度N）中给定字符串P（长度m）的出现次数，
- 您对T的后缀数组使用二进制搜索（就像您建议的那样）
- 但是使用LCParrays作为辅助数据结构可以加快速度 。 更具体地说，您生成一个特殊版本的LCParrays（我将其称为LCP-LR）并使用它。
使用标准二进制搜索（ 没有 LCP信息）的问题是，在您需要进行的每个O（log N）比较中 ，将P与后缀数组的当前条目进行比较，这意味着完整的字符串比较到m个字符。 因此复杂度为O（m * log N）。
LCP-LRarrays通过以下方式帮助将其提高到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）-lookup告诉你M和M’，lcp（M，M’）的最长公共前缀。
您已经知道（从上一步开始）M本身具有与P：lcp（P，M）= k共同的k个字符的前缀。 现在有三种可能性：
- 情况1：k
- 情况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’就足够了。
- 情况1：k
-
我们继续递归。
总体效果是不会将P的字符与文本的任何字符进行多次比较 。 字符比较的总数以m为界，因此总复杂度确实为O（m + log N）。
显然，剩下的关键问题是我们如何预先计算LCP-LR，以便它能够在O（1）时间内告诉我们后缀数组的任何两个条目之间的lcp？ 正如您所说，标准LCParrays仅告诉您连续条目的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）。
此外，还有一种直接的递归算法，用于在标准LCParrays的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的出现次数相对应。
最长公共前缀（LCP）是后缀树中的最低公共祖先（LCA）。 拥有最低公共祖先后，您可以计算从LCA分支出来的节点数。 这将为您提供后缀树中模式的出现次数。 这是LCP和LCA之间的关系。