algorithm - 使用 LRS 数组增强的 factor oracle 查找多个字符串的最长公共(public)子串

Question

我们可以使用带后缀链接 ( paper here ) 的 factor-oracle 来计算多个字符串的最长公共(public)子串吗？这里，substring 表示原始字符串的任何部分。例如“abc”是“ffabcgg”的子字符串，而“abg”不是。

我找到了一种计算两个字符串的最大长度公共(public)子串的方法 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时，在我的笔记本电脑上可以在200ms内解决问题。 , 使用因子 oracle。

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来解决，效率很高，但我想知道是否有使用factor oracle来解决的方法。我对此很感兴趣，因为 factor oracle 很容易构造(30 行 C++，suffix-array 大约需要 60 行，而 suffix-tree 需要 150 行)，而且它比 suffix-array 和 suffix-tree 运行得更快。

你可以在this OnlineJudge中测试你第一个问题的方法，以及 here 中的第二个问题.

Answer 1

Can we use a factor-oracle with suffix link (paper here) to compute the longest common substring of multiple strings?

我认为该算法不是很合适(它旨在分解单个字符串)，但您可以通过使用唯一分隔符连接原始字符串来使用它。

给定abcdefg和hijcdekl和mncdop，找到最长公共(public)子串cd:

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

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