2つの大きな配列で最も長い文字列の一致を得るために使用するアルゴリズムはどれですか？

Question

問題は説明が簡単です：2つの大きな配列（32ビットの整数値）があり、与えられた数の連続した位置（n）を超えるすべての共通の配列を見つけなければなりません。例えば

、N = 3と比較するための配列の場合：

a = [1, 3, 5, 7, 3, 2, 7, 4, 6, 7, 2, 1, 0, 4, 6] 
b = [2, 5, 7, 3, 2, 3, 4, 5, 6, 3, 2, 7, 4, 6, 0] 

algoritmhは、二つの配列を返すべきである：最初の配列に、

r0 = [5, 7, 3, 2] 
r1 = [3, 2, 7, 4, 6] 

（またはそれをその相対位置および連続するバイトの数が一致した場合）。

私は良い点はLongest Common Substring Algorithmだと思っていますが、誰かが私の問題によく合ったアルゴリズムを知っているかもしれません。私が正しくあなたを理解し、nは、 その後I'deはボイヤー - ムーアの検索アルゴリズムのバリエーションを使用する配列の最小サイズである場合

Answer 1

私は接尾辞木を使用してLCSを見つけるためのアルゴリズムを考えます完璧なフィット感です。同じ方法で接尾辞ツリーを構築しますが、最終段階では、両方の文字列の子孫を持つ最も深いノードは探していません。両方の文字列の子孫を持つn以上の深さのすべてのノードを探しています。

Answer 2

は（http://en.wikipedia.org/wiki/Boyer_moore）

Answer 3

あなたが参照しているウィキペディアのページのアルゴリズムは、あなたが望むものをほぼ正確に行うと思います。最長の回答だけを保持するのではなく、一定のサイズ以上のすべての回答を保持するように修正する必要があります。たとえば、そのページの動的プログラミングソリューションは、次のように変更できます。

function LCSubstr(S[1..m], T[1..n], min_size) 
    L := array(1..m, 1..n) 
    ret := {} 
    for i := 1..m 
     for j := 1..n 
      if S[i] = T[j] 
       if i = 1 or j = 1 
        L[i,j] := 1 
       else 
        L[i,j] := L[i-1,j-1] + 1 
       if L[i,j] >= min_size 
        ret := ret ∪ {S[i-z+1..z]} 
    return 

これは、接頭辞と最長一致を含みます。それらは、Lに見つかった文字列を追跡し、それが拡張子を持つことがわかったときにリターン・セットから接頭辞を取り除くことによって除外することができます。