У меня есть строка, которая может иметь повторяющийся шаблон символа, например
'xyzzyxxyzzyxxyzzyx'
Мне нужно написать регулярное выражение, которое заменило бы такую строку наименьшим повторяющимся шаблоном:
'xyzzyxxyzzyxxyzzyx' becomes 'xyzzyx',
'abcbaccbaabcbaccbaabcbaccba' becomes 'abcbaccba'
Используйте следующее:
> re.sub(r'(.+?)\1+', r'\1', 'xyzzyxxyzzyxxyzzyx')
'xyzzyx'
> re.sub(r'(.+?)\1+', r'\1', 'abcbaccbaabcbaccbaabcbaccba')
'abcbaccba'
> re.sub(r'(.+?)\1+', r'\1', 'iiiiiiiiiiiiiiiiii')
'i'
Он в основном соответствует шаблону, который повторяется (.+?)\1+ и удаляет все, кроме повторяющегося шаблона, который фиксируется в первой группе \1. Также обратите внимание, что использование неохотного квалификатора здесь, т.е. +?, заставит regex backtrack довольно много.
DEMO.
Поскольку вам нужен самый маленький повторяющийся шаблон, для вас должно работать следующее:
re.sub(r'^(.+?)\1+$', r'\1', input_string)
Якоря ^ и $ убедитесь, что вы не получаете совпадений в середине строки, и используя .+? вместо просто .+, вы получите самый короткий шаблон (сравните результаты с помощью строка как 'aaaaaaaaaa').
Попробуйте этот шаблон регулярного выражения и запишите первую группу:
^(.+?)\1+$
^ якорь для начала строки/строки. любой символ, кроме символов новой строки+ для обозначения наименьшего появления 1? делает + ленивым, а не жадным, поэтому дает вам кратчайший шаблон() группа захвата\1+ backreference с квантором, чтобы обозначить, что шаблон должен
повторять по крайней мере один раз$ якорь для конца строки/строкиПротестируйте его здесь: Rubular
Вышеупомянутое решение сильно влияет на производительность. Если вы знаете, какие символы не разрешены в этих строках, вы можете использовать отрицательный набор символов, который исключает обратное отслеживание. Например, если пробелы не допускаются, то
^([^\s]+)\1+$