временная сложность регулярного выражения в java

Я написал следующее java, используя регулярное выражение, чтобы найти повторяющуюся String в String 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"); 
      }

источник

2016-11-30 maya

Я понятия не имею, почему это становится помеченным как «запрос рекомендаций», но, похоже, он не сделал много для решения проблемы. – chrylis

Вам нужно выяснить, как работает matcher.find(). Как он ищет строку и когда она останавливается. – Sedrick

Я собираюсь принять дикое предположение и сказать, что он равен сложности matcher.find() – Sedrick

Регулярные выражения могут быть реализованы конечными автоматами. Таким образом, statemachine с некоторым фиксированным числом состояний и фиксированным максимальным числом (T) переходов между этими состояниями.

Для каждого символа переход выполняется до тех пор, пока он не будет отклонен или принят.

Значит, у вас есть O (String.length() * T) или O (String.length()), поскольку T является константой.

источник

2016-11-30 20:18:28

временная сложность регулярного выражения в java

ответ

Смежные вопросы