Хабрахабр: Коллективные / Блоги / Захабренные Голосов: 10 Адрес блога: http://habrahabr.ru/blog/ Добавлен: 2007-10-24 18:05:40 блограйдером Robin_Bad

Программирование / Catastrophic backtracking в регулярных выражениях

2011-11-04 20:05:31 (читать в оригинале)

Можно ли простой и вроде невинной регуляркой убить систему? Да, можно.

Например:

>>> r = '(a+)*b'

Просто — да. Невинно — вроде да. Конечно неумно, потому что скобки и звездочка лишние, но должно работать. Попробуем:

>>> re.findall('(a+)*b', 'aaaaaab')
['aaaaaa']

Круто, работает, пошли пить пиво.

А нет…