Соответствие шаблону Java идет в бесконечный цикл

Question

Друг дал мне этот кусок кода и сказал, что есть ошибка. И да, этот код работает вечно.

Ответ, который я получил:

Он работает в течение> 10 ^ 15 лет, прежде чем что-либо печатать.

public class Match {
     public static void main(String[] args) {
         Pattern p = Pattern.compile("(aa|aab?)+");
         int count = 0;
         for(String s = ""; s.length() < 200; s += "a")
             if (p.matcher(s).matches())
                 count++;
         System.out.println(count);
     }
}

Я не совсем понял, почему я вижу это поведение, я новичок в Java, у вас есть какие-либо предложения?

Answer 1

Шаблон, который вы используете, в соответствии с OWASP известен как злое регулярное выражение (большую часть времени они знают, о чем говорят):

https://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS

Это в основном соответствует aa ИЛИ aa или aab (поскольку b необязательно, если добавить ?)

Подобное Regex уязвимо для атаки ReDoS или Regex Denial of Service.

Так что да, разберитесь, что вы хотите соответствовать. Я предлагаю в приведенном выше примере вы должны просто сопоставить aa, без необходимости групп, повторения или чередования:

Pattern p = Pattern.compile("aa");

Также, как кто-то указал, кто сейчас удалил свой пост, вы не должны использовать + = для добавления к строкам. Вы должны использовать StringBuffer вместо:

public class Match {
  public static void main(String[] args) {
    Pattern p = Pattern.compile("aa");
    StringBuffer buffy = new StringBuffer(200);
    int count = 0;
    for(int i = 0; i < 200; i++){
      buffy.append("a")
      if (p.matcher(buffy.toString()).matches()){
        count++;
      }
    }
    System.out.println(count);
  }
}

Answer 2

Эта программа была из презентации Java-головоломки Джоша Блоха и Билла Пью @ Devoxx'10 смотреть ее здесь .Я думаю, что их объяснение будет лучшим.

Это на слайде 31. Но не пропускайте ни одного слайда, оно полно веселья.

Answer 3

Регулярное выражение (aa|aab?)+ - это то, которое обрабатывается механизмом регулярных выражений особенно долго.Их красочно называют злые регулярные выражения .Это похоже на пример (a|aa)+ по ссылке.Этот конкретный очень медленно работает со строкой, состоящей полностью из a s.

. Этот код проверяет регулярное выражение зла на все более длинных строках a s, вплоть до длины 200, так что, безусловно,должно занять много времени, и он не печатает, пока не закончится цикл.Мне было бы интересно узнать, откуда взялась цифра за 10 ^ 15 лет.

Edit

ОК, 10 ^ 15 (и фактически весь фрагмент кода в вопросе)с этот доклад , слайд 37. Спасибо zengr за эту ссылку.Самая важная часть информации для вопроса - то, что проверка для этого регулярного выражения занимает время, которое экспоненциально в длине строки.В частности, это O (2 ^ (n / 2)), поэтому проверка последней строки занимает в 2 ^ 99 (или около того) раз больше, чем первая.