求Java 11中可触发灾难性回溯的无反向引用正则表达式示例

Java 9 及之后的版本对正则表达式引擎做了针对性优化，像 (x+x+)+y 这类经典的嵌套重复分组，会被自动优化为等价的非回溯结构（比如 (xx+)+y），所以没法再触发预期的灾难性回溯了。不过依然存在一些无反向引用的正则模式，能绕过这些优化，引发指数级的回溯爆炸。

有效示例：(a+b+)+c #

当匹配一个由大量 ab 重复组成但**没有结尾的 c**的字符串时，这个正则就会触发灾难性回溯。

原理说明

这个正则的结构是：外层分组 (a+b+)+ 要求重复匹配「一个或多个 a 后跟一个或多个 b」的组合，最后必须匹配 c。当输入字符串是 ababab...ab（比如100个连续的ab）且没有c时，引擎会尝试所有可能的分组拆分方式：

• 先尝试把整个字符串作为一组 (a+b+) → 不匹配（因为最后没有c）
• 再拆分前99个ab为一组，最后一个ab单独一组 → 还是不匹配
• 不断拆分出更多的组合，每一次拆分都会产生指数级的尝试次数，最终导致回溯爆炸。

代码验证

public class RegexBacktrackTest {
    public static void main(String[] args) {
        // 构造100个"ab"组成的字符串，无结尾的c
        StringBuilder input = new StringBuilder();
        for (int i = 0; i < 100; i++) {
            input.append("ab");
        }
        String regex = "(a+b+)+c";
        
        long start = System.currentTimeMillis();
        try {
            boolean match = input.toString().matches(regex);
            System.out.println("匹配结果：" + match);
        } catch (Exception e) {
            e.printStackTrace();
        }
        long end = System.currentTimeMillis();
        System.out.println("耗时：" + (end - start) + "ms");
    }
}

运行这段代码你会发现，耗时会随着输入长度的增加呈指数级增长——比如100个ab可能需要几秒，150个就会卡住很久，这就是灾难性回溯的典型表现。

另一个可选示例：((a|b)+)+c #

类似地，当输入是大量交替的a和b（比如ababab...ab）且无c时，引擎会因为尝试所有可能的交替组合拆分，同样触发指数级回溯。

内容的提问来源于stack exchange，提问作者Kaerber