如何使用后缀数组和 LCP 数组查找字符串的子串？

Question

如果我们按字典顺序排列一个字符串的所有 distinct 个子串，我们需要第 i 个子串

1.) 是否可以使用 suffix array and LCP array 找到它？

2.) 如果是，我们该怎么做？是否可以在 O(Nlog^N) 中完成，同时使用时间复杂度为 O(Nlog^2N) 的 Manber & Myers 创建后缀数组，或者在使用时间复杂度为 O(N) 的 kasai 算法创建 LCP 数组时)?

Answer 1

是的，可以使用后缀数组和 LCP 数组来完成。

假设您知道如何计算后缀数组和 LCP 数组。

让 p[] 表示后缀数组 lcp[] 表示 LCP 数组。

创建一个数组，用于存储不同子字符串的数量，直到 i'th 等级后缀。这可以使用此公式计算。有关详细信息，请参阅 Here

设cum[]表示累加数组，计算如下：

cum[0] = n - p[0];
for i = 1 to n do:
    cum[i] = cum[i-1] + (n - p[i] - lcp[i])

现在要查找 i'th 子字符串，只需在累积数组 cum[] 中找到 i 的下限，这将为您提供子字符串应该开始和打印的后缀等级所有字符直到

的长度

i - cum[pos-1] + lcp[pos] // i lies between cum[pos-1] and cum[pos] so for finding 
                          // length of sub string starting from cum[pos-1] we should 
                          // subtract cum[pos-1] from i and add lcp[pos] as it is 
                          // common string between current rank suffix and 
                          // previous rank suffix.

其中 pos 是值 return 的下限。

以上整个过程可以总结如下：

string ithSubstring(int i){
    pos = lower_bound(cum , cum + n , i);
    return S.substr(arr[pos] , i - cum[pos-1] + lcp[pos]);// considering S as original character string 
}

对于后缀数组、LCP 及以上逻辑的完整实现，您可以参见Here

如何使用后缀数组和 LCP 数组查找字符串的子串？

How to find ith substring of a string using suffix array and LCP array?

c++

string

algorithm

time-complexity

suffix-array