java 中正则表达式的时间复杂度

Question

我通过使用正则表达式在字符串 s 中查找重复的字符串，写了以下 java。现在我试着找出它的复杂性，如果有人知道它的复杂性是什么，请告诉我。

           String s = "ABCABCAAAABBBBCCAAABCGABCABC";

           Pattern pattern = Pattern.compile("(?:([ABC])(?!\1)([ABC])\1\2)+");
           Matcher matcher = pattern.matcher(s);

           while (matcher.find()) {
              System.out.print("FOUND");
           }

Answer 1

正则表达式can/are 由有限状态机实现。因此状态机具有一些固定数量的状态和这些状态之间固定的最大转换数 (T)。

对每个字符进行转换，直到被拒绝或接受。

所以你有 O( String.length() * T) 或 O( String.length() ) 因为 T 是一个常数。