Regex соответствует самой длинной повторяющейся подстроке

Ответ 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

Ответ 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']

Ответ 3

Регулярные выражения могут быть полезны при решении этого вопроса, но я не думаю, что вы можете сделать это как одно выражение, так как вы хотите найти самый длинный успешный матч, тогда как регулярные выражения просто ищут первое совпадение, которое они могут найти. Жадность может быть использована для настройки, совпадение которой сначала найдено (раньше или позже в строке), но я не могу придумать способ предпочесть более раннюю более длинную подстроку над более поздней подстрокой, а также предпочитая более позднюю, более длинную подстрока по более ранней, более короткой подстроке.

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

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'

Ответ 4

Здесь длинный ish script, который делает то, что вы просите. Он в основном проходит через вашу входную строку, сокращает ее на единицу, а затем снова проходит через нее. Когда все возможные совпадения найдены, он возвращает один из самых длинных. Можно настроить его так, чтобы возвращались все самые длинные совпадения, а не только один, но я оставлю это вам.

Это довольно рудиментарный код, но, надеюсь, вы получите его суть.

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

Ответ 5

Не уверен, думал ли кто-нибудь об этом...

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";