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

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

Это не сопоставление с шаблоном, это шаблон распознавание , которое принципиально отличается и потенциально намного сложнее.

Однако можно было найти простой тип шаблона, демонстрируемый этой строкойusing (код 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 ²) времени и в постоянном пространстве.