假设你有一根绳子(例如针).它的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)/
注意:我故意没有提到任何特定的正则表达方言.请说明您在答案中使用的是哪一个.
正如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是输入的长度.尝试使用非常作为输入来查看差异.我想在很多regexp引擎的情况下,缩减版本也更快.
表达方式
NEE(d(L(E))?)|?EED(L(E)?)|?EDL(E)|?DLE
将查找长度为3或更长的子串.
正如vhallac所指出的,生成的正则表达式有点冗余,可以进行优化.除了提议的Emacs工具之外,还有一个我希望在这里有帮助的Perl软件包Regexp::Optimizer,但第一个正则表达式的快速检查失败了.
请注意,默认情况下,许多regexp引擎执行非重叠搜索.请根据您的问题要求进行检查.