RegEx отнимает слишком много времени и памяти

Question

У меня есть этот шаблон RegEx

    ^(\\d|\\w)+\\..*

, и это мой вход

    (1) nu11111111111111
    (2) nu1111111111111111111
    (3) nu1111111111111111111111111111111111111

Время, затраченное на вход 2, больше, чем на вход 1, и возвращает Несоответствие результат.Но для ввода 3 я не получил никакого ответа даже после 30 минут выполнения.Я также наблюдаю за памятью, и она постоянно увеличивается.

Ниже приведен фрагмент кода:

    String input1 = "nu11111111111111";
    String input2 = "nu1111111111111111111";
    String input3 = "nu1111111111111111111111111111111111111";
    try
    {

        if (input3.matches("^(\\d|\\w)+\\..*"))
        {
            System.out.println("Matched");
        }
        else
        {
            System.out.println("Not Matched");
        }
    }
    catch (Exception e)
    {
        e.printStackTrace();
    }

Answer 1

Это еще один случай катастрофического возврата, поскольку \d уже включен в \w.Поскольку совпадений не найдено, механизм регулярных выражений пытается вернуться к каждой возможной комбинации совпадений либо \w, либо \d против вашей серии 1 с, что довольно много.

Чтобы получить представление о происходящем, см. https://regex101.com/r/4fRRpc/1/ и перейдите к отладчику регулярных выражений.При этом используется шаблон PCRE без оптимизации запуска, что должно быть очень похоже на то, что, по-видимому, делает java в этом случае.

Для вашего регулярного выражения вместо этого используйте ^\\w+\\..*.

Answer 2

Этот движок Java regex жалок.

› time perl -E'say /^(\d|\w)+\..*/ ? "Matched" : "Not Matched" for qw(nu11111111111111 nu1111111111111111111 nu1111111111111111111111111111111111111)'
Not Matched
Not Matched
Not Matched

real    0m0,009s
user    0m0,006s
sys     0m0,003s

Попробуйте RE2 , он не возвращается и имеет привязки Java.