Строка Неизвестный шаблон соответствия

Question

Я хочу, чтобы определить неизвестный образец в виде строки, например, как,

s = 112468112468112468112468112468.

Итак, в этой строке мы можем ясно видеть, что 112468 является повторяющимся образцом. Я искал на google совсем немного, чтобы найти некоторые алгоритмы, которые могли бы мне помочь, но я мог видеть только те, которые находят данный шаблон в строке, такой как алгоритм Бойера-Мура и т. Д.

Что я сейчас делаю, чтобы найти эти повторяющиеся неизвестный образец является то, что

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] 
      } 
    } 
    } 
} 

Хотя это работает для данной строки, используя окно сравнения 4 литер, он может очень хорошо работать не для какой-то другой строки. Кто-нибудь знает лучшее решение этого.

Благодаря

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 ²) время и постоянное пространство.