regex - 在大海捞针中查找字符串*和*其子字符串

Question

假设您有一个字符串(例如 needle )。它的 19 个连续子串是:

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

如果我要构建一个正则表达式来匹配，在大海捞针中，我可以简单地执行任何子字符串:

/(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^3) 空间相比，压缩版本只需要 O(n^2) 空间，其中 n是输入的长度。用 extraordinarily 试试这个作为输入以查看差异。我想压缩版本也更快，有许多正则表达式引擎。

表达方式
nee(d(l(e)?)?)?|eed(l(e)?)?|edl(e)?|dle
将寻找长度为 3 或更长的子串。

正如 vhallac 所指出的，生成的正则表达式有点多余，可以优化。除了建议的 Emacs 工具外，还有一个 Perl 包 Regexp::Optimizer我希望能在这里有所帮助，但是第一个正则表达式的快速检查失败了。

请注意，许多正则表达式引擎默认执行非重叠搜索。请根据您的问题的要求进行检查。