使用使用LRS数组增强的因子oracle查找多个字符串的最长公共子字符串

Question

我们可以使用带后缀链接的factor-oracle(此处为纸)来计算多个字符串的最长公共子字符串吗？这里,substring表示原始字符串的任何部分.例如,"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 在我的笔记本电脑上解决200ms内的问题.

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

我知道这两个问题都可以使用后缀数组和后缀树来高效解决,但我想知道是否有一个方法使用因子oracle来解决它.我对此感兴趣,因为oracle因素易于构造(30行C++,后缀数组需要大约60,后缀树需要150),并且运行速度比后缀数组和后缀树快.

您可以在此OnlineJudge中测试第一个问题的方法,以及此处的第二个问题.

Answer 1

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

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

给定abcdefg和hijcdekl，mncdop找到最长公共子串cd：

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

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