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

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)< /code>, $^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

Answer 2

您可以在单个正则表达式中完成此操作，只需从结果列表中手动选择最长的匹配项即可。

def longestrepeating(strg):
    regex = re.compile(r"(?=(.+)\1)")
    matches = regex.findall(strg)
    if matches:
        return max(matches, key=len)

这将为您提供（因为 re.findall() 返回匹配捕获组的列表，即使匹配本身的长度为零）：

>>> longestrepeating("yabyababyab")
'abyab'
>>> longestrepeating("10100101")
'010'
>>> strings = ["56712453289", "22010110100", "5555555", "1919191919", 
               "191919191919", "2323191919191919"]
>>> [longestrepeating(s) for s in strings]
[None, '101', '555', '1919', '191919', '191919']

Answer 3

这是一个很长的脚本，可以满足您的要求。它基本上会遍历您的输入字符串，将其缩短一，然后再次遍历它。一旦找到所有可能的匹配项，它就会返回最长的匹配项之一。可以对其进行调整，以便返回所有最长的匹配项，而不是仅返回一个，但我将把它留给您。

这是非常基本的代码，但希望您能理解它的要点。

use v5.10;
use strict;
use warnings;

while (<DATA>) {
    chomp;
    print "$_ : ";
    my $longest = foo($_);
    if ($longest) {
        say $longest;
    } else {
        say "No matches found";
    }
}

sub foo {
    my $num = shift;
    my @hits;
    for my $i (0 .. length($num)) {
        my $part = substr $num, $i;
        push @hits, $part =~ /(.+)(?=\1)/g;
    }
    my $long = shift @hits;
    for (@hits) {
        if (length($long) < length) {
            $long = $_;
        }
    }
    return $long;
}

__DATA__
56712453289
22010110100
5555555
1919191919
191919191919
2323191919191919

Answer 4

不确定是否有人想到过这一点...

my $originalstring="pdxabababqababqh1234112341";

my $max=int(length($originalstring)/2);
my @result;
foreach my $n (reverse(1..$max)) {
    @result=$originalstring=~m/(.{$n})\1/g;
    last if @result;
}

print join(",",@result),"\n";

最长的双倍匹配不能超过原始字符串长度的一半，所以我们从那里开始倒数。

如果怀疑匹配项相对于原始字符串的长度来说很小，那么这个想法可以颠倒过来……我们不是向下计数直到找到匹配项，而是向上计数直到没有更多匹配项。然后我们需要备份 1 并给出结果。我们还需要在正则表达式中的 $n 后面放置一个逗号。

my $n;
foreach (1..$max) {
    unless (@result=$originalstring=~m/(.{$_,})\1/g) {
        $n=--$_;
        last;
    }
}
@result=$originalstring=~m/(.{$n})\1/g;

print join(",",@result),"\n";

Answer 5

正则表达式有助于解决这个问题，但我认为您不能将其作为单个表达式来完成，因为您想要找到最长的成功匹配，而正则表达式只是查找它们的第一个匹配可以找到。贪婪可以用来调整首先找到哪个匹配（字符串中较早和较晚的匹配），但我想不出一种方法来选择较早、较长的子字符串而不是较晚的子字符串，较短的子字符串，同时也更喜欢较晚的，较长的子字符串而不是较早的，较短的子字符串。

使用正则表达式的一种方法是按降序迭代可能的长度，并在找到指定长度的匹配项后立即退出：

my $s = '01011010';
my $one = undef;
for(my $i = int (length($s) / 2); $i > 0; --$i)
{
  if($s =~ m/(.{$i})\1/)
  {
    $one = $1;
    last;
  }
}
# now $one is '101'