使用LRS數組增強的因子oracle查找多個串的最長公共子串

我們可以使用帶有後綴鏈接的因子oracle（paper here）來計算多個串的最長公共子串嗎？這裏，子串表示原始字符串的任何部分。例如「abc」是「ffabcgg」的子串，而「abg」則不是。使用LRS數組增強的因子oracle查找多個串的最長公共子串

我找到了一種方法來計算兩個字符串s1和s2的最大長度公共子字符串。它通過使用不在其中的字符（例如'$'）連接兩個字符串來工作。然後，對於長度爲i >= |s1| + 2的連接字符串s的每個前綴，我們計算其LRS（最長重複後綴）長度lrs[i]和sp[i]（其LRS的第一次出現的結束位置）。最後，答案是

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

我已經寫了使用此方法，可以在200ms內解決我的筆記本電腦時|s1|+|s2| <= 200000問題，運用因子oracle的C++程序。

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的因素很容易構建（30行C++，後綴數組需要大約60，後綴樹需要150），並且運行速度比後綴數組和後綴樹快。

您可以在this OnlineJudge中測試您的第一個問題的方法，並在here中測試第二個問題。

來源

2012-08-14 Ray

@jogojapan非常感謝您的耐心等待！我應該爲我可憐的英語道歉。 – Ray 2012-08-15 01:57:40

根本不是（我也不是母語的人）。無論如何，我認爲在SO上有關於因素神諭的問題真是太棒了！ – jogojapan 2012-08-15 02:00:05

@Ray：你能/你在任何地方分享你的因子oracle構建實施嗎？我對這個話題很感興趣，而且我通常比正式的論文更好地閱讀源代碼:) – 2015-01-21 22:34:58

我們可以用一個因子甲骨文後綴鏈接（紙這裏）來計算多個字符串的最長公共子？

我不認爲算法是一個非常不錯的選擇（它的設計因素單個字符串），但你可以通過一個獨特的分離器串聯的原始字符串中使用它。

鑑於abcdefg和hijcdekl和mncdop，發現最長的公共子cd：

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

由於其線性的時間和空間算法的一部分，該因子甲骨文很快找回輸入字符串作爲之間的破發點搜尋共同因素的部分原因（獨特的加入者提供並立即提示停止擴展到目前爲止發現的最佳因素）。

來源

2017-02-21 06:45:59

使用LRS數組增強的因子oracle查找多個串的最長公共子串

回答

相關問題