Ответ 1

Ответ на вопрос 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 будет следующим:

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

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

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

Предположим, что нет доступных переменных lookbehind.

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

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

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

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

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

Можно просто заменить все соответствия следующего выражения на $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:
--------------------
..X.X..
..X.X..
....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..
.X.X...
.X.X...

result: 1 (.)


Test #7:
--------------------
.X..X..
.X..X..
.X..X..

result: 2 (.X)


Test #8:
--------------------
XXX
XXX
XXX

result: 3 (XXX)


Test #9:
--------------------
X.X.X
XXXXX
XXXXX
.X.X.

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.....
B.X..X..
C.....
XXX
XXX
XXX
.

result: 8 (3458.XXX)

Ответ 2

Изменить

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

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

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

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

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

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

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

где n - число. Это примерно так же сложно, как сопоставление языка a ⁿ b ⁿ c ⁿ который является каноническим примером для контекстно-зависимого языка. p >

Мы можем легко сопоставить первую строку и использовать некоторый код 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, который обеспечивает аналогичную семантику. Таким образом,

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

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

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

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

Ответ 3

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

Основное .NET-решение

Вы, ребята, сказали в комментариях, что с .NET это будет легко, но поскольку ответа пока нет, я думал, что напишу.

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

В любом случае, вот шаблон:

(?<=                  # lookbehind counts position of X into stack
  ^(?:(?<a>).)*       # push an empty capture on the 'a' stack for each character
                      # in front of X
)                     # end of lookbehind

X                     # match X

(?=.*\n               # lookahead checks that there are two more Xs right below
  (?:(?<-a>)(?<b>).)* # while we can pop an element from stack 'a', push an
                      # element onto 'b' and consume a character
  (?(a)(?!))          # make sure that stack 'a' is empty
  X.*\n               # match X and the rest of the line
  (?:(?<-b>).)*       # while we can pop an element from stack 'b', and consume
                      # a character
  (?(b)(?!))          # make sure that stack 'b' is empty
  X                   # match a final X
)                     # end of lookahead

Этот шаблон должен использоваться с RegexOptions.Multiline для ^ для соответствия началу строк (и, очевидно, с RegexOptions.IgnorePatternWhitespace для работы режима freespacing).

Вот несколько дополнительных комментариев:

Поместив все, кроме начального X, в обратные, у нас нет проблем с совпадающими совпадениями или даже с совпадениями, начинающимися в одной строке. Тем не менее, lookbehind должен иметь переменную длину, что, безусловно, ограничивает любое решение такого типа .NET.

Остальное полагается на хорошее понимание балансирующих групп. Здесь я не буду подробно останавливаться на этом, потому что он делает для довольно длинные ответы сам по себе. (см. MSDN и этот пост в блоге для еще больше информации)

Образ просто совпадает с ^.*, поэтому все до начала строки, но для каждого . мы нажимаем пустой захват на стек a, тем самым подсчитывая позицию нашего X как размер стек.

Затем, после использования остальной части строки в lookahead, мы снова сопоставляем только .*, но прежде чем потреблять каждый ., мы выкладываем один элемент из стека a (что приводит к ошибке, один раз a пуст) и нажмите пустой захват на b (чтобы мы не забыли, сколько символов должно быть для третьей строки).

Чтобы убедиться, что мы действительно опустошили весь стек, мы используем (?(a)(?!)). Это условный шаблон, который пытается сопоставить (?!), если стек a не пуст (и просто пропущен иначе). И (?!) - пустой отрицательный результат, который всегда терпит неудачу. Следовательно, это просто кодирует: "a не пусто", иначе, продолжить ".

Теперь, когда мы знаем, что мы потребляем именно нужное количество символов в новой строке, мы пытаемся сопоставить X и остальную часть строки. Затем мы снова повторяем тот же процесс со стеком b. Теперь нет необходимости нажимать на любой новый стек, потому что, если это сработает, мы закончили. Мы проверим, что после этого b пуст и соответствует третьему X.

Наконец, примечание по оптимизации: этот шаблон по-прежнему работает, если все повторения завернуты в атомарные группы (тем самым эмулируя притяжательные квантификаторы, которые не поддерживаются .NET)! Это сэкономит много времени. Более того, , если мы помещаем по меньшей мере кванторы квантов стека в атомных группах, мы можем избавиться от проверок (?(...)(?!)) (поскольку они нужны только для случаев, когда предыдущее повторение должно было отступить).

Полное .NET-решение

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

Как обсуждалось в комментариях, это решение имеет один недостаток: он считает совпадающие совпадения. Например.

..X..
..X..
..X..
..X..

Дает два совпадения: один в первом и второй во второй строке. Мы бы хотели избежать этого и сообщать только одно совпадение (или два, если есть 6-8 X и три, если есть от 9 до 11 X и т.д.). Более того, мы хотим сообщить о матчах на 1, 4, 7,... X.

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

Однако есть уловка .NET переменной длины lookbehind использует другую уникальную .NET-функцию, RightToLeftMode, в которой шаблон читается (и сопоставляется) справа налево. Обычно это не нужно беспокоить нас, но когда мы объединяем это с балансировочными группами, мы можем быть в для некоторых неприятных сюрпризов, В частности, при рассмотрении того, как развиваются наши стеки захвата, нам нужно построить (и прочитать) выражение справа налево (или снизу вверх).

Итак, когда вы читаете следующее выражение (и мои аннотации), начинайте в конце внешнего вида (вам придется немного прокручивать) - то есть непосредственно перед единственным X верхнего уровня; затем прочитайте весь путь до вершины. А потом продолжайте искать.

(?<=                  
  # note that the lookbehind below does NOT affect the state of stack 'a'!
  # in fact, negative lookarounds can never change any capturing state.
  # this is because they have to fail for the engine to continue matching.
  # and if they fail, the engine needs to backtrack out of them, in which
  # case the previous capturing state will be restored.
  (?<!                # if we get here, there is another X on top of the last
                      # one in the loop, and the pattern fails
    ^                 # make sure we reached the beginning of the line
    (?(a)(?!))        # make sure that stack 'a' is empty
    (?:(?<-a>).)*     # while we can pop an element from stack 'a', and consume
                      # a character
    X.*\n             # consume the next line and a potential X
  )
  # at this point we know that there are less than 3 Xs in the same column
  # above this position. but there might still be one or two more. these
  # are the cases we now have to eliminate, and we use a nested negative
  # lookbehind for this. the lookbehind simply checks the next row and
  # asserts that there is no further X in the same column.
  # this, together with the loop, below means that the X we are going to match
  # is either the topmost in its column or preceded by an integer multiple of 3
  # Xs - exactly what we are looking for.
  (?:

    # at this point we've advanced the lookbehind "cursor" by exactly 3 Xs
    # in the same column, AND we've restored the same amount of captures on
    # stack 'a', so we're left in exactly the same state as before and can
    # potentially match another 3 Xs upwards this way.
    # the fact that stack 'a' is unaffected by a full iteration of this loop is
    # also crucial for the later (lookahead) part to work regardless of the
    # amount of Xs we've looked at here.

    ^                 # make sure we reached the beginning of the line
    (?(c)(?!))        # make sure that stack 'a' is empty
    (?:(?<-c>)(?<a>).)* # while we can pop an element from stack 'c', push an
                      # element onto 'a' and consume a character
    X.*\n             # consume the next line and a potential X
    (?(b)(?!))        # make sure that stack 'b' is empty
    (?:(?<-b>)(?<c>).)* # while we can pop an element from stack 'b', push an
                      # element onto 'c' and consume a character
    X.*\n             # consume the next line and a potential X
    (?(a)(?!))        # make sure that stack 'a' is empty
    (?:(?<-a>)(?<b>).)* # while we can pop an element from stack 'a', push an
                      # element onto 'b' and consume a character
    X.*\n             # consume the next line and a potential X
  )*                  # this non-capturing group will match exactly 3 leading
                      # Xs in the same column. we repeat this group 0 or more
                      # times to match an integer-multiple of 3 occurrences.
  ^                   # make sure we reached the beginning of the line
  (?:(?<a>).)*        # push an empty capture on the 'a' stack for each
                      # character in front of X
)                     # end of lookbehind (or rather beginning)

# the rest is the same as before    

X                     # match X
(?=.*\n               # lookahead checks that there are two more Xs right below
  (?:(?<-a>)(?<b>).)* # while we can pop an element from stack 'a', push an
                      # element onto 'b' and consume a character
  (?(a)(?!))          # make sure that stack 'a' is empty
  X.*\n               # match X and the rest of the line
  (?:(?<-b>).)*       # while we can pop an element from stack 'b', and consume
                      # a character
  (?(b)(?!))          # make sure that stack 'b' is empty
  X                   # match a final X
)                     # end of lookahead

Рабочая демонстрация на RegexHero.net.

В этот раз я вкратце объяснил все правильные варианты. Поэтому, если вы прочтете шаблон так, как я рекомендовал выше, вы получите объяснение правильно, когда оно вам понадобится...

Теперь это был один адский зверь. Но теперь он удовлетворяет всей спецификации и показывает, насколько на самом деле мощный синтаксис .NET regex. И, хотя это кажется довольно ужасным, я думаю (как только вы осознаете право налево) это гораздо легче понять, чем сопоставимое решение с PCRE (с использованием рекурсии или иным образом).

Как упоминал Kobi в комментарии ниже, это может быть сокращено, если вы согласитесь, что ваши результаты найдены в нескольких захватах одного совпадения (например, если у вас есть столбец 7 X, вы получаете только одно совпадение, но с двумя захватами в определенной группе). Вы можете сделать это, повторив основную (lookahead) часть 1 или более раз и захватив начальную X (поместите все в lookahead, хотя). Тогда lookbehind не нужно учитывать тройки X s, но нужно только проверить, нет ли ведущего X. Это, вероятно, уменьшит размер шаблона пополам.

Частичное решение PCRE

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

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

Qtax (OP) предоставил блестящее решение для его первого вопроса (проверяя, содержит ли строка какой-либо X -column), используя группы самореференции для подсчета. Это очень элегантное и компактное решение. Но поскольку каждое совпадение идет от начала строки до X, которая запускает столбец, а совпадения не могут перекрываться, мы не можем получить несколько совпадений в строке. Мы могли бы попытаться поставить все в нужное положение (так что ничего не сопоставимо), но два совпадения с нулевой шириной также никогда не будут начинаться с одной позиции - так что мы по-прежнему будем получать только одно соответствие для каждой строки-кандидата.

Однако действительно возможно решить, по крайней мере, первую часть вопроса 2 с помощью PCRE: подсчитайте количество столбцов, начинающихся в каждой строке (и, следовательно, общее количество столбцов X). Поскольку мы не можем получить этот счет в виде отдельных совпадений (см. Предыдущий параграф), и мы не можем получить этот счет в виде отдельных групп или захватов (поскольку PCRE предоставляет только фиксированное и конечное количество захватов, в отличие от .NET.). Вместо этого мы можем кодировать количество столбцов в совпадениях.

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

Фактически реализация этой концепции в регулярном выражении намного сложнее, чем она может сначала звучать (и это уже звучит довольно сложно). Во всяком случае, вот оно:

^                        
(?:(?|
  (?(5)(?![\s\S]*+\5))      
  (?!(?!)()()) 
  (?=
    (?:
      .                  
      (?=                
        .*+\n            
        ( \3? . )   
        .*+\n        
        ( \4? . )    
      )
    )*?              
    X .*+\n          
    \3               
    X .*+\n          
    \4               
  )
  ()
|
  (?(5)(?=[\s\S]*+\5)|(?!))
  (?:
    .
    (?=
      .*+\n
      ( \1? .)
      .*+\n
      ( \2? .)
    )
  )+?
  (?=
    (?<=X).*+\n
    (\1)         
    (?<=X).*+\n
    (\2)         
    (?<=X)     
  )
  (?=
    ([\s\S])   
    [\s\S]*
    ([\s\S] (?(6)\6))
  )
){2})+

(На самом деле, это немного легче, чем это - см. ответ Qtax для того, как упростить этот подход. В любом случае я оставлю этот подход по академическим причинам, поскольку из него можно извлечь некоторые очень продвинутые и интересные методы - см. резюме в конце.)

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

Итак, посмотрим на внешний слой лука из ада:

^                        
(?:(?|
  checkForNextColumn
|
  countAndAdvance
){2})+

Итак, наши матчи снова привязаны к началу строк. Тогда мы имеем a (?:...{2})+, что означает четное число повторений чего-то. И это что-то вроде чередования двух подшаблонов. Эти подшаблоны представляют собой шаги, упомянутые выше. Первый проверяет, что есть другой столбец, начинающийся в текущей строке, второй регистрирует счетчик и подготавливает состояние двигателя для другого приложения первого подшаблона. Таким образом, управление дается второму шаблону - первый проверяет только на другой столбец, используя lookahead и, следовательно, шаблон с нулевой шириной. Вот почему я не могу просто обернуть все в +, но должен сделать объект {2})+ - иначе компонент нулевой ширины будет проверяться только один раз; что необходимая оптимизация применяется почти ко всем двигателям, чтобы избежать бесконечных циклов с такими шаблонами, как (a*)+.

Есть еще одна (очень важная деталь): я использовал (?|...) для чередования. При такой группировке каждая альтернатива начинается с того же номера группы. Следовательно, в /(?|(a)|(b))/ оба a и b могут быть записаны в группу 1. Это ключевой трюк, который позволяет "общаться" между подшаблонами, поскольку они могут изменять одни и те же группы.

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

^(?:(?|
  (?(5)(?![\s\S]*+\5))       # if group 5 has matched before make sure that
                             # it didn't match empty
  checkForNextColumn         # contains 4 capturing groups
  ()                         # this is group 5, match empty
|
  (?(5)(?=[\s\S]*+\5)|(?!))  # make sure that group 5 is defined and that it
                             # matched empty
  advanceEngineState         # contains 4 capturing groups
  (?=
    ([\s\S])                 # this is group 5, match non-empty
    [\s\S]*                  # advance to the end very end of the string
    ([\s\S] (?(6)\6))             # add a character from the end of the string to
                             # group 6
  )
){2})+

Итак, в конце каждой альтернативы мы аннулируем условие для этой альтернативы, даже начинать сопоставление. В конце второй альтернативы мы также будем включать символ в группу 6, используя технику, описанную Qtax. Это шаг подсчета. I.e., group 6 будет содержать столько символов, сколько столбцов, начинающихся в текущей строке.

Теперь checkForNextColumn будет действительно просто решением Qtax внутри lookahead. Однако для этого требуется еще одно изменение, и чтобы оправдать это, мы сначала рассмотрим advanceEngineState.

Давайте подумаем о том, как мы хотим изменить состояние, так как решение Qtax соответствует второму столбцу в строке. Скажем, у нас есть вход

..X..X..
..X..X..
..X..X..

и мы хотим найти второй столбец. Это можно было бы сделать, начав совпадение с позиции сразу после первого X и имея группы \1 и \2, уже инициализированные для первых трех символов (..X) строк 2 и 3 соответственно (вместо этого из них пустые).

Теперь попробуйте сделать это: сопоставьте все до и включите следующий X, который запустит столбец, затем заполните две группы соответствующими префиксами строки для использования в шаблоне checkForNextColumn. Это опять-таки довольно много шаблона Qtax, за исключением того, что мы подсчитываем X в (вместо того, чтобы останавливаться прямо перед ним), и что нам нужно добавить захват в отдельную группу. Итак, вот advanceEngineState:

(?:
  .
  (?=
    .*+\n
    ( \1? .)
    .*+\n
    ( \2? .)
  )
)+?
(?=
  (?<=X) .*+\n
  (\1)        
  (?<=X) .*+\n
  (\2)        
  (?<=X)
)

Обратите внимание, как я превратил X в lookbehinds, чтобы продолжить один символ и как эффективно копировать окончательное содержимое \1 в \3, а затем \2 в \4.

Итак, если мы теперь используем решение Qtax как checkForNextColumn в lookahead, используя группы \3 и \4 вместо \1 и \2, мы должны сделать.

Но как мы можем сделать эти группы \3 и \4 вместо \1 и \2? Мы могли бы запустить шаблон с ()(), который всегда соответствовал бы, не затрагивая курсор двигателя, но увеличивая количество групп на 2. Однако это проблематично: это сбрасывает группы 1 и 2 на пустые строки, что , если, мы найдем второй столбец, advanceEngineState будет находиться в несогласованном состоянии (поскольку глобальная позиция движка была продвинута, но группы подсчета снова равны нулю). Поэтому мы хотим, чтобы эти две группы вошли в шаблон, но не влияли на то, что они в настоящее время захватывают. Мы можем сделать это, используя что-то, что я уже упоминал в .NET-решениях: группы в негативных образах не влияют на захваченное содержимое (потому что движок должен отступить от поискового запроса, чтобы продолжить). Следовательно, мы можем использовать (?!(?!)()()) (отрицательный результат, который никогда не может привести к сбою шаблона), чтобы включить в наш шаблон два набора круглых скобок, которые никогда не используются. Это позволяет нам работать с группами 3 и 4 в нашем первом подшаблоне, сохраняя при этом группы 1 и 2 нетронутыми для второй итерации вторых подшаблонов. В заключение это checkForNextColumn:

(?!(?!)()()) 
(?=
  (?:
    .                  
    (?=                
      .*+\n            
      ( \3? . )   
      .*+\n        
      ( \4? . )    
    )
  )*?              
  X .*+\n          
  \3               
  X .*+\n          
  \4               
)

Что, по большей части, действительно выглядит действительно знакомым.

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

Да, это действительно работает (живая демонстрация).

Обратите внимание, что это (как и основное .NET-решение) будет превышать столбцы длиной более 3 X. Я полагаю, что можно исправить этот счет с помощью lookaheads (аналогично тому, как выглядит полное решение .NET), но это остается как упражнение для читателя.

Немного досадно, что базовая проблема этого решения уже очень запутана и раздувает решение (75% строк - это в основном только копии решения Qtax). Потому что окружающие рамки имеют некоторые действительно интересные техники и уроки:

• Мы можем иметь несколько подшаблонов, которые выполняют конкретные задачи сопоставления/подсчета, и "общаться" через взаимные группы захвата, помещая их в чередование (?|...) и зацикливая на них.
• Мы можем принудительно применять альтернативы нулевой ширины, обертывая их в конечном кванторе, например {2}, перед тем как положить все в +.
• Номера групп могут быть пропущены в одном подшаблоне (без влияния на захваченное содержимое), помещая их в неустранимый негативный вид, например (?!(?!)()).
• Элемент управления можно передавать назад и вперед между подшаблонами, захватывая что-то или ничего в определенной группе, которая проверяется при входе в чередование.

Это позволяет использовать некоторые очень мощные вычисления (я видел утверждения о том, что PCRE на самом деле является Turing-complete), хотя это, безусловно, неправильный подход для продуктивного использования. Но все же попытка понять (и придумать) такие решения может быть очень сложной и полезной задачей при решении проблем.

Ответ 4

Если вы хотите найти один "вертикальный" шаблон, вот решение. Если вы хотите также соответствовать "горизонтальному" шаблону, попробуйте сделать это с отдельным соответствием, возможно, проверив совпадение позиций соответствия. Помните, что компьютер не знает, что такое линия. Это произвольная вещь, навязанная людьми. Строка - это просто одномерная последовательность, где мы обозначаем некоторый символ (символы) как конечную строку.

#!/usr/local/perls/perl-5.18.0/bin/perl
use v5.10;

my $pattern = qr/XXX/p;

my $string =<<'HERE';
....X.......
..X..X...X....
X.X...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;
    }

Ответ 5

Вы можете повернуть изображение, а затем выполнить поиск XXX.

Ответ 6

Мой подход к сопоставлению вертикальных шаблонов с использованием PHP.

Прежде всего, поверните наш вход на 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
.
.
.

Теперь это может показаться странным, но на самом деле приближает нас, поскольку теперь мы можем просто preg_match_all() над ним:

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

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