Алгоритм поиска наиболее повторяющейся последовательности в строке (тандемные повторы)

Требуется найти наиболее повторяемую последовательность в строке. Под повторениями имеется в виду любая непрерывная комбинация символов (тандемный повтор). Как это сделать?

Можно использовать комбинацию re.findall() (со специальным паттерном) и функции max():

import re

# extended sample string
s = 'asdfewfUBAUBAUBAUBAUBAasdkjnfencsADADADAD sometext'

def find_longest_rep(s):
    result = max(re.findall(r'((\w+?)\2+)', s), key=lambda t: len(t[0]))
    return result[0]

print(find_longest_rep(s))

Результат:

UBAUBAUBAUBAUBA

О паттерне:

  • ((\w+?)\2+):
    • (...) — первая и самая отдаленная группа захвата;
    • (\w+?) — вторая группа захвата, включает любую последовательность символов без пробелов; квантификатор +? обозначает совпадение от одного до неограниченного количества раз, причем за как можно меньшее количество раз; совпадения расшираются по мере необходимости;
    • \2+ — совпадает с тем же текстом, который был недавно захвачен второй группой.

Спасибо Roman Perekhrest.