Ответьте на вопрос 1

Чтобы ответить на первый вопрос, можно было бы использовать:

 (?xm) # ignore comments and whitespace, ^ matches beginning of line ^ # beginning of line (?: . # any character except \n (?= # lookahead .*+\n # go to next line ( \1?+ . ) # add a character to the 1st capturing group .*+\n # next line ( \2?+ . ) # add a character to the 2nd capturing group ) )*? # repeat as few times as needed X .*+\n # X on the first line and advance to next line \1?+ # if 1st capturing group is defined, use it, consuming exactly the same number of characters as on the first line X .*+\n # X on the 2nd line and advance to next line \2?+ # if 2st capturing group is defined, use it, consuming exactly the same number of characters as on the first line X # X on the 3rd line 

Демо-версия

Это выражение работает в Perl, PCRE, Java и должно работать в .NET.

Выражение использует lookaheads с самонастраивающимися группами захвата, чтобы добавить символ для каждого повторения lookahead (это используется для «подсчета»).

\1?+ Означает, что \1 соответствует (или определен) потребляет его и не возвращает (не отступать). В этом случае это эквивалентно (?(1) \1 ) . Что означает соответствие \1 если \1 определено.

polygenelubricants объясняет эти виды взглядов с обратными ссылками очень хорошо в его ответе. Как мы можем сопоставить ^ nb ^ n с Java regex? , (Он также написал о других впечатляющих трюках для Java regex с участием обратных ссылок и обратных ссылок).

Ответьте на вопрос 2

Обычное совпадение

Когда вы используете совпадение и требуете ответа (количества) в количестве совпадений, тогда ответ на вопрос 2 будет следующим:

Он не может быть непосредственно решен в ароматах регулярных выражений, которые имеют ограниченный вид. В то время как другие варианты, такие как Java и .NET, могут (как, например, в .NET-решении m.buettner ).

Таким образом, регулярные регулярные выражения в Perl и PCRE (PHP и т. Д.) Не могут напрямую ответить на этот вопрос в этом случае.

(Semi?) Доказательство

Предположим, что нет переменных lookbehd переменной длины.

Вы должны каким-то образом подсчитать количество символов в строке перед X
Единственный способ сделать это – сопоставить их, и поскольку нет доступных переменных lookbehind, вы должны начать матч (по крайней мере) в начале строки.
Если вы начинаете матч в начале строки, вы можете получить не более одного совпадения в каждой строке.

Поскольку в строке может быть несколько вхождений, это не будет считать их всех и не даст правильного ответа.

Длина / косвенное решение

С другой стороны, если мы принимаем ответ как длину результата совпадения или замены, тогда на второй вопрос можно ответить в PCRE и Perl (и других вариантах).

Это решение основано на / вдохновлено хорошим «частичным решением PCRE от m.buettner» .

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

 ^ (?: (?: # match .+? characters . (?= # counting the same number on the following two lines .*+\n ( \1?+ . ) .*+\n ( \2?+ . ) ) )+? (?<= X ) # till the above consumes an X (?= # that matches the following conditions .*+\n \1?+ (?<= X ) .*+\n \2?+ (?<= X ) ) (?= # count the number of matches .*+\n ( \3?+ . ) # the number of matches = length of $3 ) )* # repeat as long as there are matches on this line .*\n? # remove the rest of the line 

Что в Perl можно было бы написать как:

 $in =~ s/regex/$3/gmx; $count = length $in; 

Демо-версия

Это выражение похоже на решение вопроса 1 выше, с некоторыми изменениями, включающими X в символы, совпадающие в первом взгляде, завернутые квантором и подсчитывающие количество совпадений квантификатора.

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

Испытательные случаи

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

 Test #0: -------------------- X X X result: 1 (X) Test #1: -------------------- ..X.... ..X.... ..X.... result: 1 (.) Test #2: -------------------- ..XX. ..XX. ....X.. result: 1 (.) Test #3: -------------------- ..X.... ..X.... ...X... result: 0 () Test #4: -------------------- ..X.... ...X... ..X.... result: 0 () Test #5: -------------------- ....X.. .X..X.. .X..... result: 0 () Test #6: -------------------- .X..X.. .XX.. .XX.. result: 1 (.) Test #7: -------------------- .X..X.. .X..X.. .X..X.. result: 2 (.X) Test #8: -------------------- XXX XXX XXX result: 3 (XXX) Test #9: -------------------- XXX XXXXX XXXXX .XX result: 5 (XXXXX) Test #10: -------------------- 1....X....... 2..X..X...X.... 3X.X...X..X..... 4X....XXXXXX..... 5X..XXX........... 6.....X.......... 7.........X....X 8..X......X....X.... 9..X......X....X....X... A....X..... BX.X.. C..... XXX XXX XXX . result: 8 (3458.XXX) 

редактировать

Следующие решения имеют две серьезные проблемы:

1. Они не могут совпадать с несколькими последовательностями XXX , начинающимися в одной строке, так как pos слишком много.
2. Второе решение неверно: оно соответствует последовательным строкам, где два X находятся друг над другом. Там не обязательно должно быть три подряд.

Таким образом, все upvotes (и щедрость) должны идти на любой из мнимых ответов .NET m.buettner или на увлекательный ответ PCRE от самого Qtax .

Оригинальный ответ

Это ответ с использованием вложения кода Perl в регулярные выражения. Поскольку регулярное выражение Perl может использовать код для утверждения произвольных условий внутри регулярных выражений или испускания частичных регулярных выражений, они не ограничены соответствующими регулярными языками или контекстными языками, но могут соответствовать некоторым частям языков выше в иерархии Хомского.

Язык, который вы хотите сопоставить, можно описать в терминах регулярных выражений как

 ^ .{n} X .*\n .{n} X .*\n .{n} X 

где n – число. Это примерно так же сложно, как и сопоставление языка ^{n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n}

Мы можем легко сопоставить первую строку и использовать некоторый код Perl для выделения регулярного выражения для других строк:

  /^ (.*?) X (?: .*\n (??{"." x length($1)}) X){2} /mx 

Это было коротко! Что оно делает?

• ^ (.*?) X фиксирует в начале строки, соответствует как можно меньше символов новой строки, а затем X Мы помним линию до X как группу захвата $1 .

• Мы повторяем группу два раза, которая соответствует остальной части строки, новой строке, а затем вводит регулярное выражение, которое соответствует строке той же длины, что и $1 . После этого должен быть X

Это регулярное выражение теперь будет соответствовать каждой строке, содержащей три X друг над другом.

Если мы хотим извлечь все такие последовательности, мы должны быть отличными. Поскольку последовательности могут перекрываться, например

 .X XX XX X. 

позиция, в которой начинается следующий матч, не должна проходить мимо первого X Мы можем сделать это через lookbehind и lookahead. Perl поддерживает только lookbehind с постоянной длиной, но имеет escape \K который обеспечивает аналогичную семантику. таким образом

 /^ (.*?) \KX (?=( (?: .*\n (??{"."x length($1)}) X ){2} )) /gmx 

будет соответствовать каждой последовательности из трех вертикальных Xs. Время тестирования:

 $ perl -E'my$_=join"",<>; say "===\n$1X$2" while /^(.*?)\KX(?=((?:.*\n(??{"."x length($1)})X){2}))/gmx' <<'END' ....X....... ..X..X...X.... XX..X..X..... X....XXXXXX..... X..XXX........... .....X.......... ..............X ..X...........X.... ..X...........X....X... ....X..... END === ..X..X...X.... XX..X..X..... X....XXXXX === XX..X..X..... X....XXXXXX..... X === X....XXXXXX..... X..XXX........... .....X === ..............X ..X...........X.... ..X...........X 

Примечание: это зависит от экспериментальных функций регулярного выражения, которые доступны по крайней мере с Perl 5, v10 и далее. Код был протестирован с v16 perl.

Решение без встроенного кода

Давайте посмотрим на линии

 ...X...\n ...X..\n 

Мы хотим утверждать, что ведущая ... часть каждой линии имеет одинаковую длину. Мы можем сделать это путем рекурсии с базовым случаем X.*\n :

 (X.*\n|.(?-1).)X 

Если мы привяжем это в начале строки, мы можем сопоставить два вертикальных X es. Чтобы сопоставить более двух строк, мы должны выполнить рекурсию в виде, а затем переместить позицию соответствия на следующую строку и повторить. Для этого мы просто сопоставляем .*\n

Это приводит к следующему регулярному выражению, которое может соответствовать строке с тремя вертикальными X es:

 / ^ (?: (?=( X.*\n | .(?-1). ) X) .*\n # go to next line ){2} /mx 

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

 / ^ (?= ( (?: (?= (X.*\n | .(?-1). ) X) .*\n # go to next line ){2} .* # include next line in $1 ) ) /mx 

Время тестирования:

 $ perl -E'my$_=join"",<>; say "===\n$1" while /^(?=((?:(?=(X.*\n|.(?-1).)X).*\n){2}.*))/gmx' <<'END' ....X....... ..X..X...X.... XX..X..X..... X....XXXXXX..... X..XXX........... .....X.......... ..............X ..X...........X.... ..X...........X....X... ....X..... END === ..X..X...X.... XX..X..X..... X....XXXXXX..... === XX..X..X..... X....XXXXXX..... X..XXX........... === X....XXXXXX..... X..XXX........... .....X.......... === ..............X ..X...........X.... ..X...........X....X... 

Таким образом, это работает так же, как и решение со встроенным кодом, то есть оно соответствует каждой группе строк с вертикальными X es, а не каждой группой X es. (На самом деле, это решение кажется мне более хрупким, чем встроенный код)

If you want to find a single "vertical" pattern, here's a solution. If you want to also match a "horizontal" pattern, try doing it with a separate match, perhaps checking for overlapping match positions. Remember that the computer has not idea what a line is. It's an arbitrary thing made up by humans. The string is just a one-dimensional sequence where we denote some character(s) to be a line ending.

 #!/usr/local/perls/perl-5.18.0/bin/perl use v5.10; my $pattern = qr/XXX/p; my $string =<<'HERE'; ....X....... ..X..X...X.... XX..X..X..... X....XXXXXX..... X..XXX........... .....X.......... ..............X ..X...........X.... ..X...........X....X... ....X..... HERE $transposed = transpose_string( $string ); open my $tfh, '<', \ $transposed; while( <$tfh> ) { while( /$pattern/g ) { my $pos = pos() - length( ${^MATCH} ); push @found, { row => $pos, col => $. - 1 }; pos = $pos + 1; # for overlapping matches } } # row and col are 0 based print Dumper( \@found ); use Data::Dumper; sub transpose_string { my( $string ) = @_; open my $sfh, '<', \ $string; my @transposed; while( <$sfh> ) { state $row = 0; chomp; my @chars = split //; while( my( $col, $char ) = each @chars ) { $transposed[$col][$row] = $char; } $row++; } my @line_end_positions = ( 0 ); foreach my $col ( 0 .. $#transposed ) { $transposed .= join '', @{ $transposed[$col] }; $transposed .= "\n"; } close $sfh; return $transposed; } 

You could rotate the image, and then search for XXX .

My approach to match vertical patterns using PHP.

First of all, let's rotate our input by 90°:

 // assuming $input contains your string $input = explode("\n", $input); $rotated = array(); foreach ($input as $line) { $l = strlen($line); for ($i = 0; $i < $l; $i++) { if (isset($rotated[$i])) $rotated[$i] .= $line[$i]; else $rotated[$i] = $line[$i]; } } $rotated = implode("\n", $rotated); 

Это приводит к

 ..XXX..... .......... .XX....XX. ....X..... X...X....X .X.XXX.... ..XX...... ...X...... ...X...... .XXX...... ...X..... ......... ........ ........ ....XXX ..... ... .. .. X . . . 

Now this might look strange, but actually brings us closer since we can now simply preg_match_all() over it:

 if (preg_match_all('/\bXXX\b/', $rotated, $m)) var_dump($m[0]); 

et voila:

 array(4) { [0] => string(3) "XXX" [1] => string(3) "XXX" [2] => string(3) "XXX" [3] => string(3) "XXX" } 

If you also want to match the same horizontal pattern, simply use the same expression on the non-rotated input.