複数の文字列の最長の共通部分文字列を計算するために、接尾辞リンク (ここでは紙) を持つ factor-oracle を使用できますか? ここで、部分文字列とは、元の文字列の任意の部分を意味します。たとえば、「abc」は「ffabcgg」の部分文字列ですが、「abg」はそうではありません。
s12 つの文字列との共通部分文字列の最大長を計算する方法を見つけましたs2。たとえば、「$」など、文字列に含まれていない文字を使用して 2 つの文字列を連結することによって機能します。s次に、 lengthの連結文字列の各プレフィックスについて、i >= |s1| + 2その LRS (最長繰り返しサフィックス) の長さlrs[i]とsp[i](その LRS の最初の出現位置の終了位置) を計算します。最後に、答えは
max{lrs[i]| i >= |s1| + 2 and sp[i] <= |s1|}
私は、この方法を使用する C++ プログラムを作成しました。このプログラムは、|s1|+|s2| <= 200000オラクル因子を使用すると、ラップトップで 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 を使用して高効率で解決できることはわかっていますが、factor oracle を使用して解決する方法はあるのでしょうか。factor oracle は簡単に構築でき (C++ で 30 行、suffix-array は約 60 行、suffix-tree は 150 行必要)、suffix-array や suffix-tree よりも高速に実行されるため、これに興味があります。
この OnlineJudgeで最初の問題の方法をテストし、ここで2 番目の問題をテストできます。