Регулярное выражение для соответствия самой длинной повторяющейся подстроки

Question

Я пишу регулярное выражение для проверки наличия подстроки, которая содержит как минимум 2 повторения некоторого шаблона рядом друг с другом.Я сопоставляю результат регулярного выражения с прежней строкой - если равен, то есть такой шаблон.Лучше сказать на примере: 1010 содержит шаблон 10, и он там 2 раза подряд.С другой стороны, 10210 не будет иметь такой схемы, потому что эти 10 не являются смежными.

Более того, мне нужно найти максимально длинный шаблон, и его длина должна быть не менее 1. Я написал выражение, чтобы проверить его ^.*?(.+)(\1).*?$.Чтобы найти самый длинный шаблон, я использовал не жадную версию, чтобы сопоставить что-либо до patter, затем шаблон сопоставляется с группой 1, и снова повторяется то же самое, что было найдено для group1.Тогда остальная часть строки сопоставляется, создавая равную строку.Но есть проблема в том, что регулярное выражение стремится вернуться после нахождения первого паттерна, и на самом деле не принимает во внимание, что я собираюсь сделать эти подстроки до и после как можно более коротких (оставляя остальные максимально длинными).Итак, из строки 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

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

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

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 4

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

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

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 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'