Edit

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

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

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

---

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

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

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

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

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

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

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

это был короткий! Что он делает?

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

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

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

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

.X
XX
XX
X.

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

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

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

$ perl -E'my$_=join"",<>; say "===\nX" while /^(.*?)\KX(?=((?:.*\n(??{"."x length()})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. Чтобы сопоставить более двух строк, мы должны сделать рекурсию в lookahead, а затем переместить позицию соответствия на следующую строку и повторить. Для этого мы просто совпадаем .*\n.

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

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

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

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

время проверки:

$ perl -E'my$_=join"",<>; say "===\n" 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...

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

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

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

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

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

в любом случае, вот образец:

(?<=                  # 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 для режима свободного пространства для работы).

вот некоторые дополнительные замечания:

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

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

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

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

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

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

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

в полном объеме .Net решение

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

как говорилось в комментарии, у этого решения есть один недостаток: оно учитывает перекрывающиеся матчи. Е. Г.

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

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

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

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

поэтому, когда вы читаете следующее выражение (и мои аннотации), начните с конца самого внешнего взгляда (вам нужно будет прокрутить a бит) - т. е. непосредственно перед единственным верхним уровнем 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's "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 на самом деле. И, хотя это кажется довольно ужасным, я думаю (как только вы поймете, что справа налево), это гораздо легче понять, чем сопоставимое решение с PCRE (используя рекурсию или иначе).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

^(?:(?|
  (?(5)(?![\s\S]*+))       # 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]*+)|(?!))  # 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)))             # add a character from the end of the string to
                             # group 6
  )
){2})+

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

теперь checkForNextColumn действительно будет просто решение Qtax внутри lookahead. Он нуждается в еще одной модификации, хотя и оправдать это мы будем смотреть в advanceEngineState первый.

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

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

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

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

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

обратите внимание, как я включил Xs в lookbehinds, чтобы пойти на один символ дальше, и как я эффективно копирую окончательное содержимое на и на .

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

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

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

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

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

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

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

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

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

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

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

#!/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;
    }

рабочее решение вопроса 2

это полностью возможно в Perl / PCRE! :)

Извините, я немного очень поздно для партии, но я просто хотел бы отметить, что вы можете на самом деле подсчитать количество найденных образований XXX; то есть структурировать выражение таким образом, чтобы было ровно одно совпадение на формирование при выполнении глобального совпадения. Хотя это довольно сложно.

вот это:

\A(?:(?=(?(3)[\s\S]*(?=\z))(?|.(?=.*\n(?+.).*\n(?+.))|.*\n()())+?(?<=X)(?=.*\n(?<=X).*\n(?<=X))(?=([\s\S]*\z)))(?=[\s\S]*([\s\S](?(4))))[\s\S])+[\s\S]*(?=\z)|\G(?!\A|[\s\S]?\z)

в действии regex101

Я должен, вероятно, добавить некоторые комментарии к этому! Здесь, для тех, кто заинтересован:

\A(?:
    (?=
        (?(3)[\s\S]*(?=\z))                   # Resume from where we ended last iteration

        (?|                                     # Branch-reset group used to reset 
            .(?=.*\n(?+.).*\n(?+.))         # and  to empty values when a new line
            |                                   # is reached. ".*\n" is used to skip the
            .*\n()()                            # rest of a line that is longer than the
        )+?                                     # ones below it.

        (?<=X)(?=.*\n(?<=X).*\n(?<=X))      # Find a XXX formation

        (?=([\s\S]*\z))                         # Save the rest of the line in  for 
    )                                           # when we resume looking next iteration

    (?=[\s\S]*([\s\S](?(4))))                 # For every formation found, consume another 
                                                # character at the end of the subject

    [\s\S]                                      # Consume a character so we can move on

    )+

[\s\S]*(?=\z)                                 # When all formations around found, consume
                                                # up to just before  at the subject end.

|

\G(?!\A|[\s\S]?\z)                              # Now we just need to force the rest of the 
                                                # matches. The length of  is equal to the 
                                                # number of formations. So to avoid overmatching,
                                                # we need to exclude a couple of cases.

Я боюсь; что происходит??

в основном, мы проходим через весь объект в одной повторяющейся группе без захвата, переходя от одного XXX-формирования к следующему. Для каждого найденного образования прикрепите другой символ на счетчик в конце предмета (сохраненный в \4). Нужно было преодолеть несколько препятствий:

• если мы сопоставляем все за один раз, как мы можем перейти от одной строки к другой? решение: используйте группу сброса ветвей для сброса \1 и \2 при обнаружении новой строки.

• что делать, если у нас есть большая сетка ASCII с небольшим "\nX\nX\nX" в конце? если мы потребляем предмет от одного формирования к другому, мы начнем есть в нашем счетчике. решение: потребляйте только один символ за раз и оберните формирование-поиск логика в упреждение.

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

Это было очень весело, и я хотел бы видеть больше постов подобного!

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

мой подход к соответствию вертикальным шаблонам с использованием 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]);

и вуаля:

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

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