1

我正在尝试在 C 中实现最长的公共子字符串算法，在阅读了下面的帖子之后，我真的对以下部分感到困惑：

现在，最大值是 LCP[2]=3，但它是针对 SA[1] 和 SA[2]，两者都以字符串 A 开头。所以，我们忽略它。另一方面，LCP[4]=2 用于SA[3]（对应于 B 的后缀 bc）和 SA[4]（对应于 A 的后缀 bcabc#bc）。所以，这是最长的公共子串。

我的 LCP 结果也与帖子示例不同。

https://cs.stackexchange.com/questions/9555/computing-the-longest-common-substring-of-two-strings-using-suffix-arrays

字符串 A = abcabc

字符串 B = bc

字符串分隔符：'#'

后缀数组

[#bc，abc#bc，abcabc#bc，bc，bc#bc，bcabc#bc，c，c#bc，cabc#bc]

液晶面板

[-1, 0, 3, 0, 2, 2, 0, 1, 1]

或删除第一个元素

后缀数组

[abc#bc, abcabc#bc, bc, bc#bc, bcabc#bc, c, c#bc, cabc#bc]

液晶面板

[0, 3, 0, 2, 2, 0, 1, 1]

我看到 SA[3] 对应于bc，但 SA[4] 对应（我猜）对应于#bcbc。所以，这就是让我困惑的地方。

任何人都可以澄清这一点？谢谢！

4

1 回答 1

1

我看到 SA[3] 对应于 bc，但 SA[4] 对应于（我猜）#bcbc。

在上面的任何地方都找不到#bcbc。引用说“SA[4]（对应于 A 的后缀 bcabc#bc）”，这当然是真的：

 0       1          2   3      4         5  6     7        index
[abc#bc, abcabc#bc, bc, bc#bc, bcabc#bc, c, c#bc, cabc#bc] Suffix Array
[0,      3,         0,  2,     2,        0, 1,    1]       LCP

SA[2]是B的后缀，SA[3]是A(#B)的后缀，所以最长的公共子串是bc，长度为2。

于 2013-07-08T19:03:35.790 回答