2

假设我构造了一个后缀数组，即一个整数数组，它按字典顺序给出字符串所有后缀的起始位置。

示例：对于字符串str=abcabbca，

后缀数组是：

suffixArray[] = [7 3 0 4 5 1 6 2]

解释：

i   Suffix      LCP of str and str[i..]   Length of LCP
7   a           a                           1
3   abbca       ab                          2
0   abcabbca    abcabbca                    8
4   bbca        empty string                0
5   bca         empty string                0
1   bcabbca     empty string                0
6   ca          empty string                0
2   cabbca      empty string                0

现在有了这个suffixArray构造，我想找到（字符串本身）和其他每个后缀之间的最长公共前缀（LCP）的长度。最有效的方法是什么？str

4

1 回答 1

4

根据您的评论，我假设我们可以访问 suffix 数组SA以及标准LCP数组，即一个数据结构，它告诉我们，在索引 i>0 处，suffix 的最长公共前缀的长度SA[i]及其字典前身SA[i-1]是。

我将使用字母 L 来指代我们要构建的特殊 LCP 数组，如问题中所述。我将使用字母 N 来表示输入字符串的长度str。

那么我们能做的就是：

  1. 确定str后缀数组中的位置。我们可以通过SA线性筛选来找到条目0。（解释：str是str从位置 0 开始的后缀。因此，0必须作为后缀数组的条目出现。）

  2. 假设我们找到的条目位于索引 k 处。然后我们可以设置L[k]:=N, we 因为SA[k]是字符串本身，并且有一个与自身相同的 N 个字符的前缀。

  3. 然后我们可以设置L[k-1]:=LCP[k]，L[k+1]:=LCP[k+1]因为这就是标准 LCP 的定义方式。

  4. 然后我们从 i:=k-2 倒退到 0 并设置

    L[i] := min(LCP[i+1],L[i+1])

    这是因为，在每次迭代 i 中，LCP[i+1]告诉我们相邻后缀SA[i]和的最长公共前缀SA[i+1]，并L[i+1]告诉我们先前处理的后缀SA[i+1]和输入字符串的最长公共前缀str。L[i]必须是这两者中的最小值，因为L[i]表示前缀SA[i]与 的共同str长度，并且不能长于与 共同的前缀SA[i+1]，否则它在后缀数组中的位置会更接近 k。

  5. 我们还从 i:=k+2 向前计数到 N 并设置

    L[i] := min(LCP[i],L[i-1])

    基于相同的推理。

然后所有的 N 个值L都已设置完毕，假设随机访问数组和整数比较分别为 O(1)，则花费的时间不超过 O(N)。

由于我们计算的数组长度为 N 个条目，因此 O(N) 的复杂度是最佳的。

（注意。您可以分别在 k-1 和 k+1 处开始第 4 步和第 5 步中的循环，并去掉第 3 步。额外的步骤仅用于使解释（希望）更容易理解.)

于 2012-06-19T07:26:12.563 回答