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

正規表現は、有限状態マシンで実装できます。ステートマシンは固定数のステートと、これらのステート間の遷移の固定最大数（T）を持ちます。

各文字について、それが拒否されるか、受け入れられるまで、遷移がとられます。

Tは定数であるため、O（String.length（）* T）またはO（String.length（））があります。