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

（注意：以下说明已复制到2014年4月9日的Wikipedia文章中，请参见diff。如果您在此处和Wikipedia上查看修订历史，则会发现此处的内容是第一个撰写的。请不要插入诸如“来自Wikipedia的评论”之类的评论。）

这个想法是这样的：为了找到在文本T（长度N）中给定字符串P（长度m）的出现次数，

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

使用标准二进制搜索（ 不 包含LCP信息）的问题是，在您需要进行的 每个O（log N）比较中
，您都将P与后缀数组的当前条目进行比较，这意味着up 的 完整字符串比较 至m个字符。因此复杂度为O（m * log N）。

LCP-LR阵列通过以下方式帮助将其提高到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）查找可以告诉您M和M’的最长公共前缀lcp（M，M’）。

您已经知道（从上一步开始）M本身与P共同具有k个字符的前缀：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'）。因此，在前k个字符中，M和M'与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值–如果您需要对此进行详细说明，我建议您提出一个单独的问题。

总结一下：

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