Можно ли простой и вроде невинной регуляркой убить систему? Да, можно. Например: >>> r = '(a+)*b' Просто — да. Невинно — вроде да. Конечно неумно, потому что скобки и звездочка лишние, но должно работать. Попробуем: >>> re.findall('(a+)*b', 'aaaaaab') ['aaaaaa'] Круто, работает, пошли пить пиво. А нет… Если строка, в которой ищем, не будет содержать искомого паттерна, например просто 'aaaaaa', компилятор будет пробовать найти её следующим алгоритмом: 1. Вся стока удовлетворяет 'a+', но мы не находим 'b', шаг назад. 2. Теперь 'a+' удовлетворяет только 'aaaaa' (все, кроме последней), последняя удовлетворяет повтору '*', 'b' все равно не находим, шаг назад. 3. Первое 'a+' удовлетворяет только 'aaaa', последние два 'aa' удовлетворяют повтору '*', 'b' все равно не находим, шаг назад. 4. Первое 'a+' удовлетворяет 'aa...
Комментарии
Отправить комментарий