検索アルゴリズム

Question

私は効率的な検索アルゴリズムを探しています最長最短私のコレクションはこの繰り返しパターンで作られたコレクション（整数2k）で繰り返しパターン（ノイズはありません繰り返されるパターンの間）、パターンの最後の発生は不完全である可能性があります。

例： 私は次を取得しました：[2,4,1,2,4,1,2,4,1]
私はしたいと思いますレシーブ：[2,4,1]

私が持っている：[21,1,15,22、21,1,15,22、21,1,15,22、21,1,15]
私がしたいのですがレシーブ：[21,1,15,22]

私が持っている：[3,2,3,2,5]
私が受け取るしたい：[]（ないパターンが存在しない）

（読みやすいようにスペースを追加）

Answer 1

非常にまっすぐ進むのアルゴリズムは（Pythonではなく、JavaScriptに変換する問題になりません）、次のようになります。

def check(a, width): 
    '''check if there is a repeated pattern of length |width|''' 
    for j in range(width, len(a)): 
    if a[j] != a[j-width]: 
     return False 
    return True 

def repeated(a): 
    '''find the shortest repeated pattern''' 
    for width in range(1, len(a)): 
    if check(a, width): 
     return a[:width] 
    return [] 

これは、ループ内の時間のほとんどは、かなり効率的でなければなりませんcheck()は最初の反復で右に戻りますので、基本的にはリストを1回だけ反復します。

Answer 2

グループの最初のグループと同じ番号になるまで、最初にグループに番号を追加して初期グループを構築してください（前の番号は終了します）パターン）。これをテストパターンとして使用し、失敗するまでパターンを照合します。 1つの候補であるコレクション全体（あなたの特別な最終パターンの扱いで）にマッチすれば。あなたの最初の試合を見つけた場所に戻り、あなたのパターンの最初の数字と一致する別の数字になるまであなたのグループを構築し続けます。あなたが長いものを見つけるたびに候補者を置き換えて、繰り返します。パターンがコレクション停止と同じ長さの場合（これは一致しません）。最長のパターンになる候補者がいる場合。

Answer 3

パターンの周期を考慮してこの問題に近づけることができると思います。シーケンスA []の期間は、すべてのiについてA [i + T] = A [i]となるような最小の整数Tである。あなたの場合、期間Tを見つけると、あなたが探している最短のパターンであるA [0..T-1]が完成します。 したがって、可能な限り小さい期間T = 1で開始し、シーケンスが定期的なプロパティを満たすかどうかをテストします。はいの場合、完了です（実際にはすべての要素が同じ場合にのみ発生します）。 大きなTの場合は、i = 0..A.len-T-1に対してA [i + T] = A [i]かどうかをテストする必要があります。これは単純なループです。

Answer 4

コレクションの長さがパターンの長さの倍数でなければならないことを確認して、検索を最適化することができます。コレクションのサイズがプライムである場合、パターンの長さは1のみです。つまり、すべての要素が同じでなければなりません。