Кратчайшая повторяющаяся суб-строка

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

input1 = 'dabcdbcdbcdd' ouput1 = 'bcd' input2 = 'cbabababac' output2 = 'ba' 

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

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

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

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

— следовать за —

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

2 Solutions collect form web for “Кратчайшая повторяющаяся суб-строка”

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

 (.+?)\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 [""] (Благодаря JF Sebastian!) Гарантирует, что никакой ValueError будет запущен, если нет никакого совпадения.

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

 import re def srp(s): return re.search(r'(.+?)\1+', s).group(1) print srp('dabcdbcdbcdd') # -> bcd print srp('cbabababac') # -> ba 

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

  • Regex не перестает оценивать после согласования с первым правилом с оператором OR
  • Извлечь номер дома и название улицы из строки с использованием Python Regex
  • Почему re.match ()?
  • Обратитесь к группе внутри группы с помощью Regex
  • Regex соответствует адресу с подшаблонами
  • Преобразование букв в нижний регистр
  • Регулярное выражение: сопоставить строку между двумя слэшами, если сама строка содержит экранированные слэши
  • Подсчет биграмм (пара двух слов) в файле с использованием python
  •  
    Interesting Posts for Van-Lav

    Функция децентрации в QPlainTextEdit вызывает segfault, если задействована последняя строка

    не может аутентифицироваться с помощью gcs в python

    scons: src и включают dirs

    Как сделать высоту виджета фиксированной пропорцией к ее ширине

    шаблон регулярного выражения python * работает не так, как ожидалось

    Как добавить ссылку с страницы администрирования Django одного объекта на страницу администратора связанного объекта?

    Как получить плоскую кластеризацию, соответствующую цветным кластерам в дендрограмме, созданной scipy

    Как я могу визуализировать древовидную структуру (рекурсивную) с использованием шаблона django?

    pandas намного медленнее, чем numpy?

    AttributeError: объект 'NoneType' не имеет атрибута 'get_text'

    Как эффективно применить оператор к декартовому произведению двух массивов?

    Как внутренние изображения представлены?

    Пропустите диктофон для оценки scikit learn

    загрузить код python во время выполнения

    Pythonic способ конвертировать словарь в namedtuple или другой хэшируемый dict-like?

    Python - лучший язык программирования в мире.