Здесь: http://lionet.livejournal.com/68807.html

Кратко:

Проект Google Re2 (C++) — успешная попытка [вос]создать промышленный regex движок, свободный от экспоненциальной зависимости от входных данных. Этот проект, выполненный Рассом Коксом (Russ Cox), дал возможность гуглу эффективно выполнять поиск по регулярным выражениям в программном коде, найденном гуглом в интернете...

В сентябре 2010 мир пополнится ещё одним таким must-read ресурсом по регулярным выражениям. Пьеса (!) A Play on Regular Expressions (http://sebfisch.github.com/haskell-regexp/regexp-play.pdf) (via antilamer) описывает создание ленивого, чисто функционального алгоритма, основывающегося на всё том же подходе превращения регулярки в конечный автомат. Описанный в статье алгоритм позволяет строить матчер выражений, поддерживающий любые контекстно-свободные (sic!!) грамматики.

Алгоритм, и соответствующая ему имплементация, Weighted RegExp Matching на простых выражениях обычно медленнее, чем другие библиотеки типа pcre, но у неё асимптотически лучшее поведение: O(nm) от длины входных данных и размера выражения. Пользуясь ленивостью, на некоторых бенчмарках (.*a.{20}a.*) эта Haskell-имплементация обгоняет Re2, описанный выше, по абсолютному времени выполнения.

Самое интересное, что тот же алгоритм был написан ещё и на C++ и Java, и на Java получился в два раза быстрее, несмотря на то, что алгоритм очень хорошо ложится на ОО, и может быть переносим между ОО-языками без особых изменений:

http://morepypy.blogspot.com/2010/06/jit-for-regular-expression-matching.html

Implementation                 язык          chars/s      speedup over pure Python
Pure Python code               Python           12'200       1
Python re module               C             2'500'000     205
Google's re2 implementation    C++             550'000      45
RPython implementation
  translated to C              Python          720'000      59
C++ implementation             C++            750'000       61
Java implementation            Java           1'920'000    157
RPython implementation
    with JIT                   Python       16'500'000    1352

Это, в частности, подтверждает тезис о том, что C++ не нужен: современные языки с GC и JIT просто уделывают его на традиционных для C/C++ задачах.

Комментарии по ссылке тоже рулят, но, просьба, не набегать туда, а ограничиться КСВ