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

注意：这是关于现代正则expression式可能性的一个问题。 这不是用其他方法解决这个问题的最好方法。 它的灵感来自一个较早的问题 ，但不限于正则expression式。

问题

在ASCII“图像”/艺术/地图/string，如：

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

我想找一个简单的垂直线形成三个X s：

 X X X 

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

问题（S）

使用正则expression式（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 # 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 

在线演示

这个expression式在Perl，PCRE，Java中起作用，并且应该在.NET中工作。

该expression式使用具有自引用捕获组的前瞻（lookahead）为每次重复的前瞻添加一个字符（用于“计数”）。

\1?+表示如果\1匹配（或被定义）消耗它，并且不要放弃（不要回溯）。 在这种情况下，它相当于(?(1) \1 ) 。 如果定义了\1则表示匹配\1 。

polygenelubricants在他的回答中很好地解释了这种带有反向引用的lookahead， 我们如何用Java正则expression式匹配一个^ nb ^ n？ 。 （他还写了关于Java正则expression式的其他令人印象深刻的技巧，涉及反向引用和查询。

回答问题2

平原匹配

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

它不能直接解决的正则expression式口味有限。 而Java和.NET等其他风格可能（例如在m.buettner的.NET解决scheme中 ）。

因此Perl和PCRE（PHP等）中的普通正则expression式匹配在这种情况下不能直接回答这个问题。

（半？）certificate

假定没有可变长度的lookbehinds可用。

您必须以某种方式计算X之前一行中的字符数。
唯一的方法就是匹配它们，因为没有可变长度的lookbehinds可用，所以你必须在行首开始匹配（至less）。
如果你在一条线的开始处开始比赛，那么每条线最多只能得到一场比赛。

由于每行可能有多个事件，所以这不会计算所有事件，也不会给出正确的答案。

长度/间接解决scheme

另一方面，如果我们接受答案作为匹配或replace结果的长度，那么第二个问题可以用 PCRE和Perl（以及其他的口味） 来回答 。

这个解决scheme是基于/灵感来自m.buettner的“部分PCRE解决scheme” 。

可以简单地用$3replace下面expression式的所有匹配项，将问题2（感兴趣模式的数量）的答案作为结果string的长度。

 ^ (?: (?: # 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; 

在线演示

这个expression式类似于上面问题1的解决scheme，其中一些修改是在第一个先行字符中匹配的字符中包含X ，用量词包围，并计数量词的匹配数目。

除了直接匹配之外，它与其它正则expression式（除了正则expression式之外的其他代码更为明智）是一样的，对于问题2也是可以接受的答案。

testing用例

上述解决scheme的一些testing用例和结果。 结果显示数字答案（结果string的长度），括号中的replace结果string。

 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) 

Answer 2

编辑

以下解决scheme有两个严重问题：

1. 它们不能匹配从同一行开始的多个XXX序列，因为pos太多了。
2. 第二个解决scheme是不正确的：它匹配连续的行，其中两个X在彼此之上。 不一定必须是三连胜。

因此，所有的赞扬（和赏金）应该去m.buettner的全面的.NET答案或Qtax自己的迷人的PCRE答案 。

---

原始答复

这是一个使用Perl代码embedded正则expression式的答案。 由于Perl正则expression式可以使用代码来在正则expression式中声明任意条件或者发出部分正则expression式，所以它们并不局限于匹配常规语言或者上下文无关语言，而是可以匹配乔姆斯基层次结构中更高级语言的某些部分。

你想匹配的语言可以用正则expression式来描述

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

其中n是一个数字。 这与匹配作为上下文敏感语言的规范示例的语言一样复杂。

我们可以很容易地匹配第一行，并使用一些Perl代码来发送其他行的正则expression式：

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

那很简短！ 它有什么作用？

• ^ (.*?) X在行的开始处锚定，尽可能less地匹配非换行符，然后匹配X 我们记得X作为捕获组$1 。

• 我们再次重复一个组，使其与匹配行的其余部分（换行符）重复，然后注入与$1相同长度的string的正则expression式。 之后，必须有一个X

这个正则expression式现在将匹配每个有三个Xstring。

如果我们想要提取所有这样的序列，我们必须是漂亮的。 因为序列可能重叠，例如

 .X XX XX X. 

下一场比赛开始的位置不能超过第一个X 我们可以通过向后看和前瞻来做到这一点。 Perl只支持常量lookbehind，但是提供了类似语义的\K转义。 从而

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

将匹配三个垂直Xes的每个序列。 testing时间：

 $ 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 

注意：这依赖于实验性的正​​则expression式function，至less可以从Perl 5，v10以上版本获得。 这个代码是用v16 perltesting的。

---

解决scheme没有embedded代码

让我们看看线路

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

我们要断言每条线的主导部分长度相同。 我们可以通过使用基本情况X.*\nrecursion来完成X.*\n ：

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

如果我们在一条线的开始处锚定，我们可以匹配两个垂直的X es。 要匹配两行以上的行，我们必须先向前recursion，然后将匹配位置推进到下一行，然后重复。 为此，我们只是匹配.*\n 。

这导致下面的正则expression式可以匹配一个string和三个垂直Xes：

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

但是这不够好，因为我们想要匹配所有这样的序列。 要做到这一点，我们基本上把整个正则expression式放在一个前瞻的位置。 正则expression式引擎确保每次都会提升位置以产生新的匹配。

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

testing时间：

 $ 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... 

因此，这与embedded代码的解决scheme一样可行，也就是说，它将每一组行与垂直X es匹配，而不是每个X es组。 （实际上，这个解决scheme似乎比embedded代码更脆弱）

Answer 3

首先：辉煌的问题。 我认为尝试将正则expression式引擎设置到极限是非常有益的。

基本的.NET解决scheme

你们在评论中说，使用.NET会很容易，但是由于目前还没有答案，所以我想我会写一个。

您可以使用.NET的可变长度lookbehind和平衡组来解决问题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之外的所有东西都放在周围，我们没有重叠匹配的问题，甚至在同一行开始匹配。 然而，后视必须是可变长度的，这当然会限制这种types的.NET的解决scheme。

其余依靠对平衡团队的把握。 在这里我不会详细讨论这个问题，因为它本身就是相当长的答案 。 （有关更多信息，请参阅MSDN和此博客文章 ）

lookbehind只是匹配^.* ，所以一切，直到行的开始，但为每一个. 我们把一个空的捕获物推到堆栈a ，从而把我们的X的位置计算为堆栈的大小。

然后消耗剩下的线，我们再次匹配.* ，但在每个消费之前. ，我们popup堆栈a一个元素（导致失败，一旦空），并将一个空的捕获到b （这样我们不会忘记第三行必须包含多less个字符）。

为了确保我们真的清空整个堆栈，我们使用(?(a)(?!)) 。 这是一个条件模式，如果堆栈a不是空的，它会尝试匹配(?!) ，否则就会被忽略。 而(?!)是一个空的负面预测，总是失败。 因此，这只是编码，“是不是空的？失败，否则，继续”。

现在知道我们已经在新行中消耗了恰到好处的字符数量，我们尝试匹配X和行的其余部分。 然后我们再次用堆栈b重复相同的过程。 现在没有必要推入任何新的堆栈，因为如果这个工作，我们就完成了。 我们在这之后检查b是空的，并且匹配第三个X

最后，一个优化方面的说明：如果所有的重复都包含在primefaces组中，这个模式仍然有效（从而模拟了.NET不支持的占有量词）！ 这将节省很多回溯。 而且， 如果我们至less把堆栈popup量词放在primefaces组中，我们可以去掉两个(?(...)(?!))检查（因为这些只是在需要重复的情况下才需要）原路返回）。

完整的.NET解决scheme

（只有最勇敢的冒险家才能跟着我进入我即将陷入的真正黑暗的洞穴…）

正如在评论中所讨论的，这个解决scheme有一个缺点：它计数重叠匹配。 例如

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

给出两场比赛，一场在第一场，一场在第二场。 我们希望避免这种情况，只报告一个匹配（如果有6到8个X ，则报告两个，如果有9到11个X ，则报告三个）等等。 而且，我们想在第一，第四，第七，… X报到比赛。

我们可以通过要求第一个X前面加上3个其他X的整数倍来调整上述模式，以满足我们的要求。 检查这个的基本思路是使用与之前一样的栈操作（除了我们在三个栈之间转移，所以在find三个X之后我们就开始了）。 为了做到这一点，我们必须小心一些。

虽然有一个问题。 .NET的可变长度lookbehind使用另一个.NET独特的function， RightToLeftMode ，其中模式从右到左读取（和匹配）。 通常情况下，这并不需要打扰我们，但是当我们将这些与平衡组合在一起时，我们可能会遇到一些不愉快的惊喜 。 特别是，当考虑我们的捕获栈如何演化时，我们需要从右向左（或从下向上）构build（并读取）expression式。

所以，当你阅读下面的expression式（和我的注释）时，从最外面的lookbehind（你将不得不滚动一下）开始 – 即在唯一的顶级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的正则expression式真正的强大。 而且，虽然这看起来相当可怕，但我认为（一旦你意识到从右到左的东西），这比使用PCRE的类似解决scheme（使用recursion或其他）更容易理解。

正如Kobi在下面的评论中提到的那样，如果你接受在一次比赛中多次获得你的结果（例如，如果你有一个7 X的列，你只能得到一个匹配，但是可以缩短这一点）在某个组中有2个捕获）。 您可以通过重复主（先行）部分1次或更多次并捕获最初的X （尽pipe将所有内容放在一个预览中）来完成此操作。 然后，lookbehind不需要计数X s的三元组，但是只需要检查没有前导X 这可能会减less一半的模式的大小。

部分PCRE解决scheme

（如果只有最勇敢的冒险者跟着我走过最后的解决scheme，我可能只会在下一个旅程中留下疯子…）

为了certificate我刚刚提到的上述解决scheme与PCRE的比较，我们来看看我们如何能够远程解决PCRE中的全部问题。 如果没有可变长度的向后看和平衡组，我们必须努力工作。

Qtax（OP）为他的第一个问题（检查string是否包含任何X列）提供了一个很好的解决scheme，使用自引用组进行计数。 这是一个非常优雅和紧凑的解决scheme。 但是因为每一场比赛都是从一开始就开始到开始列的X ，而且比赛不能重叠，所以我们无法得到每一场比赛的多场比赛。 我们可以试着把所有东西都放在一个前瞻的位置（所以没有任何东西是真正匹配的），但是两个零宽度的匹配也永远不会在同一位置开始 – 所以我们仍然只能得到每个候选线的一个匹配。

然而，用PCRE至less可以解决问题2的第一部分：计算从每行开始的列数（从而计算X列的总数）。 由于我们无法以单个匹配的forms得到这个计数（参见前面的段落），而且我们不能以单个组或捕获的forms得到这个计数（因为PCRE只提供固定和有限数量的捕获，而不是.NET。 ）。 我们可以做的是编码匹配的列数。

这里是如何：对于每一行我们检查是否有一列开始。 如果是这样，我们在一个捕获组中包含一个字符。 然后，在报告成功的匹配之前，我们尽可能find更多的列 – 为每个人添加一个字符到特定的组。 通过这样做，我们编码在每一行中以特定捕获的长度开始的列的数量。

实际上，在正则expression式中实现这个概念要比先听起来复杂得多（而且听起来相当复杂）。 无论如何，这里是：

 ^ (?:(?| (?(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的答案我会留下这个方法无论如何都是出于学术的原因，因为一些非常先进和有趣的技术可以从中学到 – 参见结束。）

是的，没有注释。 我想，无论如何，没有人会真正阅读它们，所以我会尝试把这个expression方式分解（我会采用自上而下的方法）。

那么让我们来看看地狱洋葱的外层：

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

所以我们的比赛再次停留在线条的起点。 那么我们有一个(?:...{2})+这意味着偶数的重复的东西。 而且这是两个子模式的交替。 这些子模式代表了我上面提到的步骤。 第一个检查在当前行中是否有另一列开始，第二个注册一个计数并为第一个子模式的另一个应用程序准备引擎的状态。 所以控制权被赋予第二种模式 – 第一种模式使用向前检查来检查另一列，因此是零宽度模式。 这就是为什么我不能简单地将所有内容都包含进来，而是必须做{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})+ 

所以在每个select结束时，我们将使这个替代的条件无效，甚至开始匹配。 在第二个select结束时，我们还将使用Qtax概述的技术将一个字符包含在第6组中。 这是计数步骤。 也就是说，第6组将包含与当前行中开始的列相同数量的字符。

现在checkForNextColumn只是Qtax的解决scheme。 它需要一个更多的修改，为了certificate这一点，我们先看看advanceEngineState 。

让我们考虑一下如何修改状态，Qtax的解决scheme可以匹配连续的第二列。 说我们有投入

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

我们想find第二列。 这可以通过从刚刚在第一个X之后的位置开始匹配并且已经将组\1和\2已经初始化到行2和3的前三个字符（ ..X ）（而不是它们是空的）。

现在让我们尝试这样做：匹配所有内容，包括下一个启动列的X ，然后使用相应的行前缀填充两个组，以在checkForNextColumn模式中使用。 这又是Qtax的模式，除了我们计算X （而不是在它之前停止），并且我们需要将捕获添加到一个单独的组中。 所以这里是advanceEngineState ：

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

请注意我是如何将X变成逆序，进一步去一个angular色，以及如何有效地将\1的最终内容复制到\3和\2的最后内容到\4 。

所以，如果我们现在使用Qtax的解决scheme作为向前看的checkForNextColumn ，使用groups \3和\4而不是\1和\2 ，我们应该完成。

但是，我们如何使这些群体\3和\4而不是\1和\2呢？ 我们可以用()()来启动模式，它总是匹配的，而不会影响引擎的光标，但增加组数为2.然而，这是有问题的：这将重置组1和2为空string， 如果我们发现第二列， advanceEngineState将处于不一致的状态（因为引擎的全局位置已经提前，但是计数组再次为零）。 所以我们希望把这两个组织纳入模式，但不影响他们目前捕获的内容。 我们可以通过利用.NET解决scheme中已经提到的一些东西来做到这一点：负向search结果中的组不会影响捕获的内容（因为引擎需要退出查找过程）。 因此，我们可以使用(?!(?!)()()) （一个不会导致模式失败的负向前向）在我们的模式中包含两组括号，这是从不使用的。 这使我们可以在第一个子模式中使用第3组和第4组，同时保持第1组和第2组下一次迭代的第二个子模式不变。 总之这是checkForNextColumn ：

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

其中，大部分看起来真的很熟悉。

所以就是这样 对一些input运行这个会给我们一个组6 ，其中包含一个捕获，每行有一个列开始 – 捕获的长度将告诉我们有多less列开始在那里。

是的，它真的有用（现场演示）。

请注意，这（如基本的.NET解决scheme）将超过超过3 X长的列。 我认为可以用向前的方式来修正这个计数（类似于完整的.NET解决scheme的后视图），但这只是给读者一个练习。

这个解决scheme的基本问题已经非常复杂并且使解决scheme（75％的线路大部分仅仅是Qtax的解决scheme的副本）变得有些不幸。 因为周围的框架有一些非常有趣的技巧和教训：

• 我们可以有多个子模式完成特定的匹配/计数任务，并通过相互捕获组进行“交stream”，将它们置于(?|...)交替循环之中。
• We can force zero-width alternatives to be carried out over and over again by wrapping them in a finite quantifier like {2} before putting everything into + .
• Group numbers can be skipped in one subpattern (without affecting the captured contents) by putting them into a never-failing negative lookahead like (?!(?!)()) .
• Control can be passed back and forth between subpatterns by capturing something or nothing in a certain group that is checked upon entering the alternation.

This allows for some very powerful computations (I've seen claims that PCRE is in fact Turing-complete) – although this is certainly the wrong approach for productive use. But still trying to understand (and come up) with such solutions can be a very challenging and somehow rewarding exercise in problem solving.

Answer 4

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

Answer 5

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

Answer 6

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.