正则表达式:回溯引擎为什么会灾难性回溯

  各模式遇到「n 个重复单元 + 一个会让匹配失败的字符 !」时 matches() 的耗时(ms,超过 2000 ms 中止记为 >2000):
    模式                         n = 16   n = 20   n = 24   n = 28
    (a+)+b                          0        0        0        0
    ^(a+)+$                         0        0        0        0
    (a|aa)+b                        0        0        0        0
    ^(?:a|ab)*$                     0        0        0        0
    (a+)+?b                         4       50      745    >2000
    (.*a){12}                       8       69      699    >2000
    ^(a+)+\1b                       4       61      978    >2000
    (a|b|ab)*?c                    17      225    >2000    >2000
    (?:x+x+)+?y                     3       38      613    >2000
  对比 a+b(n = 100000):0 ms

  原模式(懒惰)                (a+)+?b        输入 24 个 a + c:   255 ms
  原子组                    (?>a+)+?b      输入 200 万个 a + c:    15 ms
  占有量词 a++               (a++)+?b       输入 200 万个 a + c:    10 ms
  改写成 a+b                a+b            输入 200 万个 a + c:    10 ms

  (a|b)*       输入 "abab…":最长成功的长度 2000,n = 4000 时 StackOverflowError
  (?:a|b)*     输入 "abab…":最长成功的长度 2000,n = 4000 时 StackOverflowError
  [ab]*        输入 "abab…":最长成功的长度 128000,到 128000 都没有溢出
  (a|b)*+      输入 "abab…":最长成功的长度 128000,到 128000 都没有溢出
  (?:a|b)*+    输入 "abab…":最长成功的长度 128000,到 128000 都没有溢出

  包一层带截止时间的 CharSequence(200 ms):匹配超时,实际在 200 ms 后中止(没有它,这个输入会算非常久,我没有等它算完)