是-K-子串与后缀树

Question

我可怎么办下一步操作，用绳子S的后缀树，谁的顶点数量为O界函数（| S |）：

是-K - 子字符串（r） - 检查字符串r是否为s的k-子字符串，其中k-子字符串定义如下：

s的子字符串r定义为k-字符串，如果有一个分区s到子字符串，其中：

r = x1x2 ... xk; xi = s的子串。例如：s = whitething，r = within，r是s的3个子字符串。

我需要该操作来处理O（| r |）的复杂性。

我不明白如何在O（| r |）上做到这一点，因为r中的每个字符都可以是当前的分隔符，例如2-Sub-string，所以为此我必须尝试所有可能的字符作为x1和x2之间的分隔符（对于分区r = x1x2）。

任何想法？

Answer 1

引理：如果A是B和B后缀可以拆分成S最多k子，这样可以A。

证明：让B = x[1] x[2] x[3] ... x[k]。让我们扔掉分区的第一个|B| - |A|字符。我们将得到一个不超过k部分的分区。推论：如果我们有一个前缀为R的固定分区，则存在一个最佳分区，其中下一个子字符串是我们可以采用的最长分区。

该解决方案紧接着来自上述证明。我们可以使各部分只要我们能：

pos = 0 
while pos < R.length: 
     take the longest prefix of R[pos:] that is a substring of R 
     move pos after the end of this substring 

该解决方案可在线性时间内实现的：我们只是从树的根部开始，并保持只要他们去为当前角色的转变R。如果没有，我们将当前部分添加到答案并从根重新开始。