Нахождение строки * и * ее подстрок в стоге сена

Question

Предположим, у вас есть строка (например, needle).Его 19 непрерывных подстрок:

needle
needl eedle
need eedl edle
nee eed edl dle
ne ee ed dl le
n e d l

Если бы я построил регулярное выражение, чтобы сопоставить в стоге сена любую из подстрок, которые я мог бы просто сделать:выглядит действительно элегантно.Есть ли лучший способ создать регулярное выражение, которое будет жадно соответствовать любой из подстрок данной строки?

Кроме того, что, если я поставил другое ограничение, хотел бы сопоставить только подстроки длиннее порога, например, дляподстроки длиной не менее 3 символов:

/(needle|needl|eedle|need|eedl|edle|nee|eed|edl|dle)/

примечание: я специально не упомянул какой-либо конкретный диалект регулярного выражения.Пожалуйста, укажите, какой из них вы используете в своем ответе.

Answer 1

Как и предполагал Qtax, выражение

n(e(e(d(l(e)?)?)?)?)?|e(e(d(l(e)?)?)?)?|e(d(l(e)?)?)?|d(l(e)?)?|l(e)?|e

будет подходящим вариантом, если вы хотите написать явное регулярное выражение (синтаксис egrep, необязательно заменить (...)на (?:...)).Причина, по которой это лучше, чем первоначальное решение, заключается в том, что сжатой версии требуется только пространство O (n ^ 2) по сравнению с пространством O (n ^ 3) в исходной версии, где n - длина входных данных.Попробуйте это с extraordinarily в качестве ввода, чтобы увидеть разницу.Я предполагаю, что сжатая версия также быстрее со многими механизмами регулярных выражений.

Выражение

nee(d(l(e)?)?)?|eed(l(e)?)?|edl(e)?|dle

будет искать подстроки длиной 3 или более.

Как указывает vhallac, сгенерированные регулярные выражения немного избыточны и могут быть оптимизированы.Помимо предложенного инструмента Emacs, есть пакет Perl Regexp :: Optimizer , который, как я надеялся, поможет здесь, но быстрая проверка не удалась для первого регулярного выражения.

Обратите внимание, что многие регулярные выражения regexpПо умолчанию движки выполняют поиск без наложения.Проверьте это с требованиями вашей проблемы.

Answer 2

Я нашел элегантное almostsolution , в зависимости от того, насколько сильно вам нужно только одно регулярное выражение.Например, вот регулярное выражение, которое находит общую подстроку (perl) длиной 7:

"$needle\0$heystack" =~ /(.{7}).*?\0.*\1/s

Соответствующая строка находится в \ 1 .Строки не должны содержать нулевой символ, который используется в качестве разделителя.

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

Answer 3

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

Нет. Но вы можете легко сгенерировать такое выражение.

Answer 4

Возможно, вы просто ищете .*(.{1,6}).*