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

Question

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

1.) 是否可以使用 suffix array 找到它和 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 是下界返回的值。

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

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