这个Java正则表达式如何检测回文？

Question

^{这是一系列正则表达式教学文章中的第三部分。它跟随着如何使用正则表达式查找三角形数？（其中首次介绍了嵌套引用）和如何使用Java正则表达式匹配a^n b^n？（其中进一步阐述了前瞻“计数”机制）。本文介绍了一种特定形式的嵌套断言，当与嵌套引用相结合时，允许Java正则表达式匹配大多数人认为是“不可能”的回文串！}

回文串的语言是非正则的，实际上是上下文无关的（对于给定的字母表）。话虽如此，现代的正则表达式实现可以识别不止正则语言，Perl/PCRE 的递归模式和 .NET 的平衡组都可以轻松地识别回文串（请参见：相关问题）。

然而，Java 的正则表达式引擎不支持这些“高级”特性。尽管如此，“某人”^(*眨眼*)设法编写了以下正则表达式，它似乎完美地完成了任务（在 ideone.com 上也可以看到）：

public class Palindrome {
    // asserts that the entirety of the string matches the given pattern
    static String assertEntirety(String pattern) {
        return "(?<=(?=^pattern$).*)".replace("pattern", pattern);
    }

    public static void main(String[] args) {
        final String PALINDROME =
            "(?x) | (?:(.) add)+ chk"
                .replace("add", assertEntirety(".*? (\\1 \\2?)"))
                .replace("chk", assertEntirety("\\2"));

        System.out.println(PALINDROME);
        // (?x) | (?:(.) (?<=(?=^.*? (\1 \2?)$).*))+ (?<=(?=^\2$).*)
        
        String[] tests = {
            "",     // true
            "x",    // true
            "xx",   // true
            "xy",   // false
            "xyx",  // true
            "xxx",  // true
            "xxyx", // false
            "racecar",                // true
            "step on no pets",        // true
            "aManaPlanaCanalPanaMa",  // true
            "this is impossible",     // FALSE!!!
        };
        for (String test : tests) {
            System.out.printf("[%s] %s%n", test, test.matches(PALINDROME));
        }
    }
}

所以这似乎有效，但是为什么？

参考资料

• java.util.regex.Pattern
• regular-expressions.info/Freespacing (?x), Lookarounds (?=…)/(?<=…)等。

---

COMMON SENSE ALERT!!!

这不是检测回文的最佳方法；最好的情况下，它是O(N^3)。在更通用的编程语言中执行此检测既更有效率又更直观。

您不会想要使用正则表达式来检测回文，就像您不会想要使用正则表达式查找质数一样。尽管如此，您可以学习非递归非平衡组正则表达式如何检测回文，原因与学习正则表达式用于素数测试相同：它有趣，具有挑战性，具有教育意义。

相关问题

• 如何使用正则表达式检查字符串是否为回文？ - 这是“不可能的”！（除非...）
• 如何检查给定的字符串是否为回文？ - 多种语言中的非正则表达式解决方案
• 如何使用正则表达式确定数字是否为质数？

- polygenelubricants

---

关于该系列的讨论：http://meta.stackexchange.com/questions/62695/permission-to-start-a-series-of-advanced-regex-articles；此外，毫无疑问，这篇长文中可能存在拼写错误或不准确之处。请留下评论和反馈，因为我计划继续修订。 - polygenelubricants

我只想提一下，使用正则表达式来检测回文是一个特别愚蠢的想法。有更好的方法来实现它。当然可以使用这种方法来学习正则表达式，但其中的一部分教育就是知道何时不要使用它们。并不是要打击你的热情，@poly，我相信这是一篇好文章 :-) - paxdiablo

@paxdiablo：这篇文章并不是真正关于回文的，几乎和寓言并不是真正关于会说话的狮子或唱歌的驴子一样。这里有道德和教训可供学习，将其仅看作回文检测正则表达式只是皮毛而已。 - polygenelubricants

@poly - 我同意 @paxdiablo 的观点，并且认为使用正则表达式来完成复杂的任务是一个愚蠢/不好的想法。在我看来，这个问题/答案应该以不要这样做的警告为前缀，用闪烁的红色26号大写字母来提示。 - Stephen C

第四部分：https://dev59.com/XXA65IYBdhLWcg3wrQl4 - polygenelubricants

Answer 1

总体概述

我们首先从整体算法的角度来看待这个正则表达式，然后稍后再仔细研究具体的实现细节。该正则表达式几乎是以下Java代码的直接转换:

static boolean isPalindrome(String s) {
   if (s.isEmpty()) {
      return true;
   }
   String g2 = null;
   for (char ch : s.toCharArray()) {
      String g1 = String.valueOf(ch);
      // "add"
      if (g2 != null && s.endsWith(g1 + g2)) {
         g2 = g1 + g2;
      } else if (s.endsWith(g1)) {
         g2 = g1;
      } else {
         break;
      }
   }
   return s.equals(g2); // "chk"
}

这显然不是最简单/高效的Java代码来检查回文，但它能正常工作，最令人着迷的是，它几乎可以直接转换为正则表达式，并且具有几乎一对一的映射关系。以下是正则表达式，为了方便在此再次复制，并进行了注释以突出其惊人的相似之处：

//  isEmpty  _for-loop_
//       ↓  /          \
    "(?x) | (?:(.) add)+ chk"
//             \_/  ↑
//             g1   loop body                   ___g2___
//                                             /        \
           .replace("add", assertEntirety(".*? (\\1 \\2?)"))
           .replace("chk", assertEntirety("\\2"));
                           // s.equals(g2)

附件: 在ideone.com上的源代码的注释和扩展版本

(现在可以忽略assertEntirety的细节: 只需将其视为一个黑盒正则表达式机制，该机制可以对整个字符串进行断言，而不管我们当前所处的位置。)

因此，基本算法是在从左到右扫描字符串时，尝试构建一个后缀，受回文约束的影响。然后，我们检查是否能够以这种方式构建完整的字符串。如果可以，那么字符串就是一个回文。此外，作为特殊情况，空字符串显然是一个回文。

一旦理解了大局算法，我们就可以研究正则表达式模式如何实现它。

---

为什么要使用那么多String.replace？

Java中的正则表达式模式最终只是字符串，这意味着它们可以通过字符串操作来派生，就像任何字符串一样。是的，我们甚至可以使用正则表达式生成正则表达式模式——一种元正则表达式方法，如果您愿意的话。

考虑以下初始化int常量的示例（最终只包含一个数字）：

final int X = 604800;
final int Y = 60 * 60 * 24 * 7;
// now X == Y

X所分配的数字是一个字面整数：我们可以清楚地看到这个数字。对于Y来说情况并非如此，因为它使用了一个表达式，但是这个公式似乎传达了这个数字代表的思想。即使没有适当命名这些常量，我们仍然可以得到这样的想法，即Y可能表示一周中的秒数，即使我们可能不会立即知道数字值是多少。另一方面，对于X，我们确切地知道那个数字，但是我们对它所代表的含义的了解却很少。

在代码片段中使用字符串替换是一个类似的情况，但是针对字符串正则表达式模式。有时候，从简单部分系统和逻辑推导出该值（"公式"）要比显式地将模式写成一个文本字符串更有意义。在正则表达式中，这一点尤其重要，因为我们理解模式的作用比能够看到它作为一个文本字符串的外观更重要（而且由于所有额外的反斜杠，它看起来也不怎么好看）。

以下是方便起见再次复制的代码片段的一部分：

// the "formula"
     final String PALINDROME =
        "(?x) | (?:(.) add)+ chk"
           .replace("add", assertEntirety(".*? (\\1 \\2?)"))
           .replace("chk", assertEntirety("\\2"));

// the "value"
     System.out.println(PALINDROME);
     //                       ____add_____             chk_
     //               _______/            \____   _______/ \_____
     // (?x) | (?:(.) (?<=(?=^.*? (\1 \2?)$).*))+ (?<=(?=^\2$).*)
     //        |  \_/             \______/     |
     //        |   1                 2         |
     //        |_______________________________|

毫无疑问，在这种情况下，“公式”比最终的字符串“值”更易读。

当然，有更加复杂的编程方式来生成正则表达式模式，而且有可能编写出使含义变得晦涩难懂的代码，但即使是简单的字符串替换也可以产生奇妙的效果（正如本例所示）。

教训：考虑使用程序生成正则表达式模式。

---

add 如何工作？

在前两部分中已经详细讨论了 (?:(.) add)+ 结构，其中 add 是一种执行某种“计数”的断言。但有两个值得注意的特点：

• (.) 捕获到组1中，以便稍后进行反向引用
• 断言是 assertEntirety 而不仅仅是从当前位置向前查找
  • 我们将在后面更详细地讨论它；只需将其视为一种断言整个字符串的方式

应用于 add 中的 assertEntirety 的模式如下：

# prefix   _suffix_
#    ↓    /        \
    .*?   ( \1 \2? )
#         \________/   i.e. a reluctant "whatever" prefix (as short as possible)
#          group 2          followed by a suffix captured into group 2

请注意，第二组使用了可选限定符的自引用技术，在系列文章的第二部分中已经讨论过。毫无疑问，第二组是我们在这个模式中的“计数器”：它是一个后缀，在“循环”的每次迭代中，我们将尝试向左扩展它。当我们从左到右迭代每个(.)时，我们尝试将相同字符（使用反向引用\1）预先添加到我们的后缀中。

再次回想一下以上模式的Java代码翻译，为方便起见，重复如下：

if (g2 != null && s.endsWith(g1 + g2)) {   // \2? is greedy, we try this first
   g2 = g1 + g2;
} else if (s.endsWith(g1)) {    // since \2? is optional, we may also try this
   g2 = g1;
} else {        // if there's no matching suffix, we "break" out of the "loop"
   break;
}

\2?是可选的事实意味着几件事情:

• 它为自我引用提供了“基本情况”（这也是我们这样做的主要原因！）
• 由于\2?是后缀模式的一部分（因此在整个模式中出现较晚），前缀部分必须是勉强的，因此使用.*?而不是.*。这使得\2?可以行使其贪婪性。
• “计数器”也可能“重置”并给出“错误”的结果
  • 在第二部分中，我们展示了回溯?可能导致相同类型的问题重置
    • 我们通过使用占有量词?+来解决问题，但这里不适用

第三点在下一节中进一步阐述。

教训: 仔细分析模式的部分中贪婪/勉强重复之间的交互。

相关问题

• 正则表达式中.*?和.*的区别
• 正则表达式：谁更贪婪？

---

为什么我们需要一个chk阶段？

如前一节所述，可选且可回溯的\2?意味着我们的后缀在某些情况下可能会缩小。我们将逐步检查此类情况，以获取以下输入：

 x y x y z y x
↑
# Initial state, \2 is "uninitialized"
             _
(x)y x y z y x
  ↑
  # \1 captured x, \2 couldn't match \1\2 (since \2 is "uninitialized")
  #                but it could match \1 so it captured x
           ___
 x(y)x y z y x
    ↑
    # \1 captured y, \2 matched \1\2 and grew to capture yx
             _
 x y(x)y z y x
      ↑
      # \1 captured x, \2 couldn't match \1\2,
      #                but it could match \1 so it shrunk to capture x (!!!)
           ___
 x y x(y)z y x
        ↑
        # \1 captured y, \2 matched \1\2 and grew to capture yx
         _____
 x y x y(z)y x
          ↑
          # \1 captured z, \2 matched \1\2 and grew to capture zyx
       _______
 x y x y z(y)x
            ↑
            # \1 captured y, \2 matched \1\2 and grew to capture yzyx
     _________
 x y x y z y(x)
              ↑
              # \1 captured x, \2 matched \1\2 and grew to capture xyzyx

我们可以修改我们的模式（以及相应的Java代码）来省略chk阶段，并且可以看到确实发生了这种情况：

    // modified pattern without a chk phase; yields false positives!
    final String PALINDROME_BROKEN =
        "(?x) | (?:(.) add)+"
            .replace("add", assertEntirety(".*? (\\1 \\2?)"));

    String s = "xyxyzyx"; // NOT a palindrome!!!
    
    Matcher m = Pattern.compile(PALINDROME_BROKEN).matcher(s);
    if (m.matches()) {
        System.out.println(m.group(2)); // prints "xyzyx"
    }

如上所述，"xyxyzyx"并不是回文，但由于我们没有检查增长后缀是否最终成为完整字符串（在这种情况下显然没有），因此错误地报告为回文。因此，在我们的设置中，“chk”阶段（即模式\2的assertEntirety）是绝对必要的。我们需要确认我们确实成功地将后缀增长到了最后。如果是这种情况，则我们有一个回文。 教训：仔细分析任何可能的自我参考匹配的意外副作用。

---

主菜： assertEntirety

虽然我们可以编写Java正则表达式模式来检测回文，但除了assertEntirety之外，本系列的先前部分已经涵盖了所有内容。唯一的新东西是这个神秘的黑匣子，这个强大的机制神奇地使我们能够做到“不可能”的事情。

assertEntirety构造基于嵌套环视的以下元模式：

(?<=(?=^pattern$).*)

“我可以看到在我身后的某个地方，我可以向前看并看到^pattern$”

“环视”的名称意味着与我们当前位置的相关性：我们在“环视”我们周围，也许是在我们前面或后面，从我们所站立的地方。通过以这种方式将前瞻嵌套在后顾中，我们能够隐喻地“飞入天空”并查看整个画面。

将此元模式抽象为assertEntirety有点像编写预处理替换宏。到处嵌套环视可能会影响可读性和可维护性，因此我们将其封装到assertEntirety中，不仅隐藏了其内部工作的复杂性，而且通过给它一个适当的名称进一步强调了其语义。

教训：考虑抽象化元模式以隐藏复杂性并传达语义。

---

附录：关于Java中无限长度后顾

细心的读者会注意到，在assertEntirety中包含一个在后顾中的.*，使其理论最大长度为无限。不，Java没有正式支持无限长度后顾。是的，正如在这里充分证明的那样，它仍然有效。正式地，它被归类为“错误”；但是“某人”^(*眨眼*)也可以认为这是一个“隐藏的功能”。

当然，这个“错误”可能会在未来被“修复”。删除此隐藏功能将破坏解决Java正则表达式回文问题的特定解决方案。

相关问题

• Java中没有明显的最大长度的正则表达式后向查找

- polygenelubricants