我们可以使用带后缀链接的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 …