我正在尝试在 C 中实现最长的公共子字符串算法,在阅读了下面的帖子之后,我真的对以下部分感到困惑:
现在,最大值是 LCP[2]=3,但它是针对 SA[1] 和 SA[2],两者都以字符串 A 开头。所以,我们忽略它。另一方面,LCP[4]=2 用于SA[3](对应于 B 的后缀 bc)和 SA[4](对应于 A 的后缀 bcabc#bc)。所以,这是最长的公共子串。
我的 LCP 结果也与帖子示例不同。
字符串 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。所以,这就是让我困惑的地方。
任何人都可以澄清这一点?谢谢!