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

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

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

但是，Java的正则表达式引擎既不支持这些“高级”function。 然而“某人” ^{（ * 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)); } } } 

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

参考

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

---

常见的警告！

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

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

相关问题

• 如何使用正则表达式检查字符串是回文？ – 不可能”！ （除非…）
• 如何检查给定的字符串是否是回文？ – 许多语言的非正则表达式解决方案
• 如何确定一个数字是否是正则表达式的素数？

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是一个做某种“计数”的断言，已在前两部分中进行了彻底讨论。 但值得注意的是两个function：

• (.)捕获到组1中，以后允许反向引用
• 断言是assertEntirety而不仅仅是outlook我们目前的立场
  • 我们稍后会详细讨论这个问题; 只是把它想象成一种在整个字符串上断言的方法

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

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

请注意，组2是自引用的，带有可选的说明符，这是本系列第2部分中已讨论过的技术。 毋庸置疑，第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? 行使贪婪。
• “计数器”也可以“重置”并给出“错误”的结果
  • 在第2部分中，我们展示了如何回溯? 可能导致同样有问题的重置
    • 我们通过使用所有格量词?+解决了这个问题，但这不适用于此

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

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

相关问题

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

---

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

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

  xyxyzyx ↑ # Initial state, \2 is "uninitialized" _ (x)yxyzyx ↑ # \1 captured x, \2 couldn't match \1\2 (since \2 is "uninitialized") # but it could match \1 so it captured x ___ x(y)xyzyx ↑ # \1 captured y, \2 matched \1\2 and grew to capture yx _ xy(x)yzyx ↑ # \1 captured x, \2 couldn't match \1\2, # but it could match \1 so it shrunk to capture x (!!!) ___ xyx(y)zyx ↑ # \1 captured y, \2 matched \1\2 and grew to capture yx _____ xyxy(z)yx ↑ # \1 captured z, \2 matched \1\2 and grew to capture zyx _______ xyxyz(y)x ↑ # \1 captured y, \2 matched \1\2 and grew to capture yzyx _________ xyxyzy(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都已经在本系列的前几部分中介绍过了。 这里唯一新的东西是这个神秘的黑盒子，这种强大的机制让我们神奇地允许我们做“不可能”的事情。

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

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

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

“环顾”这个名字意味着与我们当前职位的相对性：我们正在寻找我们周围 ，或许是在我们所站立的前方或后方。 通过以这种方式在前瞻中嵌套前瞻，我们能够隐喻地“飞向天空”并查看整个画面。

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

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

---

附录：关于Java中无限长的lookbehind

细心的读者会注意到assertEntirety在一个assertEntirety包含一个.* ，这使得它的理论最大长度无限。 不，Java并没有正式支持无限长的外观。 是的，因为它已在这里充分展示，无论如何它仍然有效。 正式它被归类为“虫子”; 但“某人” ^{（* wink *）}也可以将其视为“隐藏的function”。

这个“错误”肯定会在将来被“修复”。 删除这个隐藏的function将打破Java regex回文问题的特定解决方案。

相关问题

• 正则表达式在Java中没有明显的最大长度