java中正則表達式的時間複雜度

我通過使用正則表達式在字符串s中查找重複的字符串來編寫以下java。現在我試圖找出它的複雜性，如果有人知道它的複雜性，請告訴我。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"); 
      }

來源

2016-11-30 maya

我不知道爲什麼這被標記爲「要求建議」，但似乎沒有做OP來解決這個問題。 – chrylis

您需要了解matcher.find（）如何工作。它如何搜索字符串以及它何時停止。 – Sedrick

我將採取瘋狂的猜測，並說它等於matcher.find（）的複雜度 – Sedrick

正則表達式可以由有限狀態機實現。因此，狀態機具有一些固定數量的狀態和這些狀態之間的轉換的固定最大數量（T）。

對於每個字符都會進行轉換直到被拒絕或接受。

所以你有O（String.length（）* T）或O（String.length（）），因爲T是一個常量。

來源

2016-11-30 20:18:28

java中正則表達式的時間複雜度

回答

相關問題