联系人列表为空，请先登录

  2. 帖子详情

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

IT小君   2021-11-10T08:33:52

这是一系列教育正则表达式文章中的第三部分。它遵循这个正则表达式如何找到三角形数？（首先引入嵌套引用）以及我们如何将 a^nb^n 与 Java 正则表达式匹配？ （其中进一步阐述了前瞻“计数”机制）。这部分介绍了一种特定形式的嵌套断言，当与嵌套引用结合使用时，Java 正则表达式可以匹配大多数人认为“不可能”的内容：回文！！

回文的语言是非常规的；它实际上是上下文无关的（对于给定的字母表）。也就是说，现代正则表达式实现不仅仅识别常规语言，而且 Perl/PCRE 的递归模式和 .NET 的平衡组可以轻松识别回文（参见：相关问题）。

但是，Java 的正则表达式引擎不支持这些“高级”功能。然而“某人” （*wink*）设法编写了以下正则表达式，它似乎可以很好地完成这项工作（另请参见 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));
        }
    }
}

所以这似乎有效，但是如何？

参考

常识警报！！！

这不是检测回文的最佳方法；这是O(N^3)最好的。以更通用的编程语言执行此检测既更有效也更直接。

您不想使用正则表达式来检测回文，原因与您不想使用正则表达式查找素数的原因相同。也就是说，您将研究非递归非平衡组正则表达式如何检测回文，原因与研究正则表达式如何用于素性测试的原因相同：它很有趣，很有挑战性，很有教育意义。

相关问题

评论(1)
IT小君

大图

我们先从整体的大图算法来看这个正则表达式，后面再仔细看看具体的实现细节。正则表达式几乎是以下 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不仅仅是从我们当前的位置向前看
    • 我们稍后会更详细地讨论这个问题；只需将其视为对整个字符串进行断言的一种方式

应用于assertEntiretyin的模式add如下：

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

请注意，第 2 组是带有可选说明符的自引用，该技术已在本系列的第 2 部分中讨论过。不用说，第 2 组是这种模式中的“计数器”：它是一个后缀，我们将在“循环”的每次迭代中尝试向左增长。当我们(.)从左到右迭代时，我们尝试将相同的字符（使用反向引用 to \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?行使它的贪婪。
  • “计数器”也可能“重置”并给出“错误”的结果
    • 在第 2 部分中，我们展示了回溯如何?导致同样有问题的重置
      • 我们使用所有格量词解决了这个问题?+，但这在这里不适用。

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

课程：仔细分析模式部分中贪婪/不情愿重复之间的相互作用。

相关问题

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

正如上一节所提到的， optional 和 backtrackable\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阶段（这是assertEntirety模式的一个\2）在我们的设置中是绝对必要的。我们需要确认我们确实设法一直增加我们的后缀。如果是这种情况，那么我们就有了一个回文。

课程：仔细分析可选的自参考匹配的任何可能意外的副作用。

主菜： assertEntirety

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

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

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

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

“环视”这个名称暗示了与我们当前位置的相对性：我们正在环顾四周，可能是在我们站立的位置的前面或后面。通过以这种方式在后视中嵌套前视，我们可以比喻性地“飞向天空”并查看整个画面。

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

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

附录：Java 中的无限长回溯

细心的读者会注意到在lookbehind中assertEntirety包含a .*，这使得它的理论最大长度是无限的。不，Java 不正式支持无限长后视。是的，正如这里已经充分展示的那样，它无论如何都可以工作。官方将其归类为“错误”；但是“某人” （*眨眼*）也可以将其视为“隐藏功能”。

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

相关问题

2021-11-10T08:33:53   回复