Сравнение шаблонов Java с бесконечным циклом

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

Я получил ответ:

Он работает в течение > 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, есть ли у вас какие-либо предложения?

Ответ 1

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

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

Он в основном соответствует aa OR aa или aab (так как b является необязательным добавлением ?)

Regex, подобный этому, уязвим для ReDoS или Regex Denial of Service Attack.

Так что да, разобраться, что вы хотите совместить. Я предлагаю в приведенном выше примере просто сопоставить 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);
  }
}

Ответ 2

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

Его в слайде 31. Но не пропустите слайды, чтобы они позабавились.

Ответ 3

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

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

Изменить

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