大局
我们先从整体大图算法来看这个正则表达式，后面再细看具体的实现细节。正则表达式几乎是对以下 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 组是我们在这个模式中的“计数器”：它是一个后缀，我们将在“循环”的每次迭代中尝试向左增长。(.)当我们从左到右进行迭代时，我们尝试将相同的字符（使用对 的反向引用\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?意味着我们的后缀在某些情况下可以缩小。我们将为此输入逐步检查这样的场景：
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有点像编写预处理替换宏。到处都有嵌套的lookarounds可能会损害可读性和可维护性，因此我们将其封装为assertEntirety，这不仅隐藏了其内部工作的复杂性，而且通过给它一个适当的名称来进一步强调其语义。
课程：考虑抽象元模式以隐藏复杂性并传达语义。
附录：关于 Java 中的无限长回溯
细心的读者会注意到其中assertEntirety包含 a .*，这使得它的理论最大长度是无限的。不，Java 不正式支持无限长度的后视。是的，因为它已经在这里得到充分证明，它无论如何都可以工作。官方将其归类为“错误”；但是“某人” （*wink*）也可以将其视为“隐藏功能”。
这个“bug”肯定有可能在未来被“修复”。移除这个隐藏的特性会破坏这个对 Java 正则表达式回文问题的特殊解决方案。
相关问题