文字列不明パターン一致

Question

s = 112468112468112468112468112468のような文字列の未知のパターンを特定したいとします。

この文字列では、112468が繰り返しパターンであることがわかります。 Googleで を検索しましたが、いくつかのアルゴリズムを見つけるのにはかなり役に立ちましたが、Boyer-Mooreアルゴリズムなどの文字列で特定のパターンを見つけることしかできませんでした。

未知のパターンはこれが4つのリテラルの比較ウィンドウを使用して、指定した文字列のために動作しますが、それは非常によく、他のいくつかの文字列では動作しない場合があり

for(i=0;i<Length of String;i++) 
{ 
    for(j=i+1;j<Length of String;j++) 
    { 
    if(s[i]==s[j] && s[i+1]==s[j+1] && s[i+2]==s[j+2] && s[i+3]==s[j+3]) 
    { 
     patternlength=j-i; 

      for(k=i;k<j;k++) 
      { 
      pattern[k]=s[i+k] 
      } 
    } 
    } 
} 

、ということです。誰かがこれに対するより良い解決策を知っていますか？

おかげ

Answer 1

これは、パターンマッチングではありません、これは根本的に異なると潜在的にはるかに困難であるパターン認識、です。しかし、この文字列によって示されるパターンの簡単な種類が（Pythonコード）を使用して発見されている可能性が

：

def find_repeated_pattern(s): 
    for i in xrange(1, len(s)/2): 
     if s == s[:i] * (len(s)/i): 
      return s[:i] 

これが原因で、すべての文字列のコピーのナイーブな実装であるが、それはさせることができ、 O（n²）の時間と一定の空間で作業してください。