正则表达式匹配最长的重复子字符串

Question

我正在编写正则表达式来检查是否存在子串,其中包含至少2个彼此相邻的模式重复.我将正则表达式的结果与前一个字符串相匹配 - 如果相等,则存在这样的模式.通过示例更好地说:1010包含模式10,并且连续系列中有2次.另一方面,10210将不具有这种模式,因为那些10不相邻.

更重要的是,我需要找到最长的模式,它的长度至少为1.我已经写了表达式来检查它^.*?(.+)(\1).*?$.为了找到最长的模式,我使用了非贪婪的版本来匹配模式之前的东西,然后模式匹配到组1并且再次匹配组1匹配的相同的东西.然后匹配其余的字符串,产生相等的字符串.但是有一个问题是正则表达式在找到第一个模式后急于返回,并且没有真正考虑到我打算在最短的时间之前和之后制作那些子串(剩下最长的可能).所以从字符串01011010我得到正确的匹配,但存储在组1中的模式只是01我除了101.

因为我相信我不能让模式"更贪婪"或者在"更多非贪婪"之前和之后变废为止,我只能想出一个让正则表达式不那么渴望的想法,但我不确定这是否可行.

更多例子:

56712453289 - no pattern - no match with former string
22010110100 - pattern 101 - match with former string (regex resulted in 22010110100 with 101 in group 1)
5555555 - pattern 555 - match
1919191919 - pattern 1919 - match
191919191919 - pattern 191919 - match
2323191919191919 - pattern 191919 - match

使用当前表达式会得到什么(使用相同的字符串):

no pattern - no match
pattern 2 - match
pattern 555 - match
pattern 1919 - match
pattern 191919 - match
pattern 23 - match

Answer 1

在Perl中,您可以通过以下方式使用一个表达式来完成(??{ code }):

$_ = '01011010';
say /(?=(.+)\1)(?!(??{ '.+?(..{' . length($^N) . ',})\1' }))/;

输出:

101

这里发生的事情是,在匹配连续的一对子串之后,我们确保使用负向前瞻,即不再有一对跟随它.

为了使较长对的表达式使用一个推迟的子表达式构造(??{ code }),它在内部(每次)评估代码并使用返回的字符串作为表达式.

它构造子表达式具有形式.+?(..{N,})\1,其中N是所述第一捕获组的当前长度(length($^N),$^N包含以前捕获组的电流值).

因此,完整表达式将具有以下形式:

(?=(.+)\1)(?!.+?(..{N,})\2}))

神奇的N(和第二个捕获组不是原始表达的"真实"/适当的捕获组).

用法示例:

use v5.10;

sub longest_rep{
    $_[0] =~ /(?=(.+)\1)(?!(??{ '.+?(..{' . length($^N) . ',})\1' }))/;
}

say longest_rep '01011010';
say longest_rep '010110101000110001';
say longest_rep '2323191919191919';
say longest_rep '22010110100';

输出:

101
10001
191919
101