6

我们可以使用带有后缀链接的因子-oracle（此处为论文）来计算多个字符串的最长公共子字符串吗？这里，子字符串表示原始字符串的任何部分。例如“abc”是“ffabcgg”的子字符串，而“abg”不是。

我找到了一种方法来计算两个字符串的最大长度公共子字符串s1和s2. 它通过使用不在其中的字符连接两个字符串来工作，例如'$'。s然后对于长度为 的连接字符串的每个前缀i >= |s1| + 2，我们计算其 LRS（最长重复后缀）长度lrs[i]和sp[i]（其 LRS 第一次出现的结束位置）。最后，答案是

max{lrs[i]| i >= |s1| + 2 and sp[i] <= |s1|}

我已经编写了一个使用这种方法的 C++ 程序，它可以在我的笔记本电脑上|s1|+|s2| <= 200000使用因子 oracle 在 200 毫秒内解决问题。

s1 = 'ffabcgg'
s2 = 'gfbcge'
s = s1+'$'+s2 
  = 'ffabcgg$gfbcge'
p: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
s:  f f a b c g g $ g f  b  c  g  e
sp: 0 1 0 0 0 0 6 0 6 1  4  5  6  0
lrs:0 1 0 0 0 0 1 0 1 1  1  2  3  0

ans = lrs[13] = 3

我知道使用 suffix-array 和 suffix-tree 可以高效地解决这两个问题，但是我想知道是否有使用因子 oracle 的方法来解决它。我对此感兴趣是因为因子 oracle 很容易构造（用 30 行 C++，suffix-array 需要大约 60，而 suffix-tree 需要 150），并且它比 suffix-array 和 suffix-tree 运行得更快。

您可以在此 OnlineJudge中测试您的第一个问题的方法，并在此处测试第二个问题。

4

1 回答 1

0

我们可以使用带有后缀链接的因子-oracle（此处为论文）来计算多个字符串的最长公共子字符串吗？

我不认为该算法非常适合（它旨在考虑单个字符串），但您可以通过将原始字符串与唯一分隔符连接来使用它。

给定abcdefgand hijcdekl，mncdop找出最长的公共子串cd：

# combine with unique joiners
>>> s = "abcdefg" + "1" + "hijcdekl" + "2" + "mncdop" 
>>> factor_oracle(s)
"cd"

作为其线性时间和空间算法的一部分，factor-oracle 快速重新发现输入字符串之间的断点，作为其搜索公共因子的一部分（独特的连接器提供并立即提示停止扩展迄今为止找到的最佳因子） .

于 2017-02-21T06:45:59.490 回答