Tag: 后缀数组

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如何帮助吗？