ASCII“图像”中的“垂直”正则表达式匹配

Question

注意：这是有关现代正则表达式口味的问题。这不是使用其他方法解决此问题的最佳方法。它是由一个较早的问题启发而来的，但是这个问题并不局限于正则表达式。

问题

在ASCII“图像” /艺术/地图/字符串中，例如：

....X.......
..X..X...X....
X.X...X..X.....
X....XXXXXX.....
X..XXX...........
.....X..........
..............X
..X...........X....
..X...........X....X...
....X.....

我想找到一个简单的垂直线3 Xs：

X
X
X

图像中的行数是可变的， 每 行的宽度也是可变的。

问题

使用正则表达式（PCRE / PHP，Perl，.NET或类似文件）可以：

1. 确定是否存在这种形式
2. 计算此类编队的数量/匹配所有编队的起点（上例中为4）

Answer 1

回答问题1

要回答第一个问题，可以使用：

(?xm)                    # ignore comments and whitespace, ^ matches beginning of line
^                        # beginning of line
(?:
    .                    # any character except \n
    (?=                  # lookahead
        .*+\n            # html" target="_blank">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

[**Online demo**](http://ideone.com/iUFxBw)

此表达式可在Perl，PCRE，Java中使用，并且应在.NET中使用。

该表达式将前瞻性与自引用捕获组配合使用，以便为每次重复的前瞻性添加一个字符（用于“计数”）。

\1?+表示\1匹配项（或已定义）是否消耗了它，并且不将其退还（不回溯）。在这种情况下，它等效于(?(1) \1 )。\1如果\1定义，则表示匹配。

问题2的答案

普通匹配

当仅使用匹配并要求匹配数中的答案（计数）时，问题2的答案将是：

不能
在有限的正则表达式中直接解决它。而其他样式如Java和.NET也可以（例如m.buettner的.NET解决方案中的样式。

因此，在这种情况下，Perl和PCRE（PHP等）中的纯正则表达式匹配无法直接回答此问题。

（半？）证明

假设没有可变长度的回溯可用。

您必须以某种方式计算X。之前一行的字符数。
唯一的方法就是匹配它们，并且由于没有可变长度的后向匹配，您必须（至少）在行的开头开始匹配。
如果您在一行的开头开始比赛，则每行最多只能有一个比赛。

由于每行可能有多次出现，因此这不会全部统计，也不会给出正确的答案。

长度/间接解决方案

另一方面，如果我们接受答案作为匹配或替换结果的长度，则 可以使用 PCRE和Perl（以及其他类型） 回答 第二个问题。

该解决方案基于m.buettner的漂亮的“部分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;

[**Online demo**](http://ideone.com/FLfOLX)

此表达式类似于上面问题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)