Сопоставьте самую длинную повторяющуюся последовательность (которая не состоит из повторяющейся последовательности)

Рассмотрим строку

aabaabaabaabaab

Очевидно, что эта строка состоит из 5 смежных входов aab, поэтому я хочу, чтобы мое регулярное выражение соответствовало aab.

Чтобы уточнить: aabaab не будет приемлемым выходом, потому что он сделал, повторяя aab. Но aab является допустимым результатом, потому что он не состоит из повторяющейся более короткой строки.

Для вопроса предположим, что может быть дополнительный текст вокруг повторяющегося сегмента (например, 11aabaabaabaabaab22 или даже xaabaabaabaabaabaa). Поэтому невозможно привязать регулярное выражение с помощью ^ или $.

Неудачная идея # 1: (.+?)\1+ Здесь вместо <ожидаемого aab отображается aa.

Неудачная идея # 2: (.+)\1+ Это фиксирует aabaab.

Можно ли сделать это с помощью чистого регулярного выражения? Если да, возможно ли это без динамической ширины?

Ответ 1

Вы можете использовать два вида, первый из которых выполняет поиск самого длинного шаблона, а второй выполняет поиск самого маленького. Второй повторяемый образец должен заканчиваться (по крайней мере) в том же положении или после повторения первого шаблона. Чтобы проверить это, вы должны зафиксировать конец строки в первом представлении и использовать обратную ссылку для этого захвата во втором просмотре.

(?=(.+)\1+(.*))(?=(.+?)\3+\2$)\3+

демо

Результат в группе 3

(?=(.+)\1+(.*))(.+?)\3+(?=\2$)\3*

Обратите внимание, что эти два шаблона регулярных выражений дают результат для одной позиции в строке. Если вы хотите знать, что является самым коротким шаблоном, который является самой длинной подстрокой, однажды повторяемой для всей строки, вы должны найти все из них и выбрать самую длинную строку susbstring с кодом. Для этого вы можете использовать шаблон для перекрывающихся результатов:

(?=(.+)\1+(.*))(?=(.+?)\3+\2$)(?=(\3+))

(с использованием группы 4)

Ответ 2

def largest_pattern(value)
  /(.+)\1+/.match(value).try("[]", 1)
end

def smallest_pattern(value)
  /^(.+?)\1+$/.match(value).try("[]", 1)
end

def largest_distinct_pattern(value)
  val = largest_pattern(value)
  if val
    while(new_val = smallest_pattern(val))
      val = new_val
    end
    val
  else
    nil
  end
end

largest_distinct_pattern("aabaabaabaabaab")
=> "aab"