Кратчайшая повторяющаяся подстрока - PullRequest
Новая
       6

Кратчайшая повторяющаяся подстрока

6 голосов
/ 26 декабря 2011

Я ищу эффективный способ извлечь самую короткую повторяющуюся подстроку. Например: 

input1 = 'dabcdbcdbcdd'
ouput1 = 'bcd'

input2 = 'cbabababac'
output2 = 'ba'

Буду признателен за любой ответ или информацию, связанную с проблемой.

Кроме того, в этом посте люди предлагают использовать регулярное выражение, например 

re=^(.*?)\1+$

чтобы найти наименьший повторяющийся узор в строке. Но такое выражение не работает в Python и всегда возвращает мне несоответствие (я новичок в Python и, возможно, я что-то пропустил?).

--- продолжение ---

Здесь критерием является поиск кратчайшего неперекрывающегося шаблона, длина которого больше единицы и имеет наибольшую общую длину.

Ответы [ 2 ]

14 голосов
/ 26 декабря 2011

Быстрое исправление для этого шаблона может быть 

(.+?)\1+

Ваше регулярное выражение не удалось, потому что оно привязало повторяющуюся строку к началу и концу строки, разрешив только строки типа abcabcabc, но не xabcabcabcx,Кроме того, минимальная длина повторяемой строки должна быть 1, а не 0 (или любая строка будет соответствовать), поэтому .+? вместо .*?.

В Python: 

>>> import re
>>> r = re.compile(r"(.+?)\1+")
>>> r.findall("cbabababac")
['ba']
>>> r.findall("dabcdbcdbcdd")
['bcd']

Но учтите, что это регулярное выражение найдет только непересекающиеся повторяющиеся совпадения, поэтому в последнем примере решение d не будет найдено, хотя это самая короткая повторяющаяся строка.Или посмотрите этот пример: здесь он не может найти abcd, потому что abc часть первого abcd была использована в первом совпадении): 

>>> r.findall("abcabcdabcd")
['abc']

Также он может вернутьнесколько совпадений, поэтому вам нужно будет найти самое короткое на втором шаге: 

>>> r.findall("abcdabcdabcabc")
['abcd', 'abc']

Лучшее решение:

Чтобы двигатель мог также найти перекрытиесовпадений, используйте 

(.+?)(?=\1)

Это позволит найти несколько строк дважды или более, если они повторяются достаточно много раз, но, безусловно, найдет все возможные повторяющиеся подстроки: 

>>> r = re.compile(r"(.+?)(?=\1)")
>>> r.findall("dabcdbcdbcdd")
['bcd', 'bcd', 'd']

Следовательно, выследует отсортировать результаты по длине и вернуть самое короткое: 

>>> min(r.findall("dabcdbcdbcdd") or [""], key=len)
'd'

or [""] (благодаря Дж.Ф. Себастьяну!) гарантирует, что ValueError не сработает, если совпадения не будет вообще.

3 голосов
/ 26 декабря 2011

^ соответствует началу строки. В вашем примере повторяющиеся подстроки не начинаются с начала. Аналогично для $. Без ^ и $ шаблон .*? всегда соответствует пустой строке. Демо 

import re

def srp(s):
    return re.search(r'(.+?)\1+', s).group(1)

print srp('dabcdbcdbcdd') # -> bcd
print srp('cbabababac')   # -> ba

Хотя он не находит самую короткую подстроку.

...