Найти повторяющуюся последовательность в подстроке

#python #регулярные_выражения #текст #подстрока

Всем привет. Задача такова - найти самую длинную повторяющуюся последовательность
в исходной подстроке.
Задач элементарно решается перебором. Но хочется одолеть её регулярными выражениями.
Текущий код:

import re

def repeat_inside(text):
    m = re.findall(r'((\w+)\2+)', text)
    print('исходный текст = {}, результат поиска = {}'.format(text, m[0][0]))
    return m[0][0]

if __name__ == '__main__':
    assert repeat_inside('aabbff') == 'aa'
    assert repeat_inside('aaaaa') == 'aaaaa'
    assert repeat_inside('aababcc') == 'abab'
    assert repeat_inside('abc') == ''
    assert repeat_inside('abcabcabab') == 'abcabc'


Результат выполнения:

исходный текст = aabbff, результат поиска = aa
исходный текст = aaaaa, результат поиска = aaaaa
исходный текст = aababcc, результат поиска = aa
Traceback (most recent call last):
  File "C:/Users/.../main.py", line 12, in 
    assert repeat_inside('aababcc') == 'abab'
AssertionError


Пробовал менять регулярное выражение на \w?((\w+)\2+). Это решает проблему с aababcc.
Но ломает другие тесты. Есть ли у кого-то идеи? Можно без ответа, просто подскажите,
пожалуйста, в какую сторону рыть.
    

Ответы

Ответ 1

Нашёл решение. Необходимо было использовать lookahead assertion (?=...). Итоговое
регулярное выражение:

re.findall(r'(?=((.+?)\2+))', text)


Итоговый код:

import re

def repeat_inside(text):
    match = re.findall(r'(?=((.+?)\2+))', text)
    return max((x[0] for x in match), key=len, default='')


if __name__ == '__main__':
    assert repeat_inside('aaaaa') == 'aaaaa', "First"
    assert repeat_inside('aabbff') == 'aa', "Second"
    assert repeat_inside('aababcc') == 'abab', "Third"
    assert repeat_inside('abc') == '', "Forth"
    assert repeat_inside('abcabcabab') == 'abcabc', "Fifth"