BZ>пруфлинк? или хотя бы объяснение на пальцах, как он обойдётся без бектрекинга, когда в паттерне много '*'?

Можно далеко не ходить, тут же на rsdn есть статьи про НКА/ДКА:
Конечные автоматы
Недетерминированные конечные автоматы

Автор(ы): Сергей Холодилов
Дата: 30.07.2007
В статье описан маленький, но всё равно интересный кусочек теории вычислений. Предназначение статьи – послужить наживкой, заглотив которую, читатели уже сами продолжат изучение этой теории.

Как проверить, является ли строка числом, e-mail'ом?

Автор(ы): Николай Меркин
Дата: 19.01.2002

Общая идея — если по паттерну построить НКА, то чтоб сматчить строчку — надо обойти этот НКА. Обойти его можно как вширь так и вглубь (аналогично обходам графа). Обход вглубь — это и есть алгоритм с откатами (бэктрекингом). Обход вширь — это это обход с запоминанием более чем одного состояния (то есть в каждый конкретный момент можем находиться в нескольких состояниях). В первом случае тратим время, во втором — память.
Каждый НКА можно преобразовать в эквивалнтный ДКА. Для ДКА обходы вширь и вглубь совпадают — так как из каждого состояния есть только один переход по заданному символу.

Для примера возьмем шаблон "a*a*b". Построим автомат:


Обход вглубь (с откатами) для строки "aaab":
^aaab q0
a^aab q1
aa^ab q1 Пошли по q1-*->q1
aaa^b q1 Пошли по q1-*->q1
aaab^ q1 Пошли по q1-*->q1, Fail, строка кончилась а q1 не терминальное состояние
aaa^b q1 Откатываемся
aaa^b q1 q1-a->q1 не подходит
aa^ab q1 Откатываемся дальше
aa^ab q2 Пошли по q1-a->q2
aaa^b q2 Пошли по q2-*->q2
aaab^ q2 Пошли по q2-*->q2, Fail, строка кончилась а q2 не терминальное состояние
aaa^b q2 Откатываемся
aaab^ q3 Пошли q2-b->q3, q3 финальное и строка кончилась — Epic win

Теперь обход вширь (уже без откатов):
^aaab {q0}
a^aab {q1} q0-a->q1
aa^ab {q1,q2} q1-*->q1,q1-a->q2
aaa^b {q1,q2} q1-*->q1,q1-a->q2,q2-*->q2
aaab^ {q1,q2q3} q1-*->q1,q2-*->q2,q2-b->q3, Win: строка кончилась, в нашем множестве состояний есть финальное

Здесь мы одновременно можем находиться во всех состояниях, поэтому худшая сложность O(l*n) где l — длина строки, n — количество сотояний. Зато откатов уже нет.

Ну и теперь преобразуем этот автомат в ДКА:


Теперь для обходя надо помнить только одно состояние, и не надо делать откаты:
^aaab q0
a^aab q1
aa^ab q2
aaa^b q2
aaab^ q3 Win: строка кончилась, состояние финальное

Очевидно, что здесь сложность O(l) где l — длина строки. Где же нас кидают? При постороении ДКА число сотояний может вырасти экспоненциально. Впрочем здесь простые шаблоны, нет альтернатив и групп (например мы не можем написать шаблон ((a*)*)*) поэтому в данном конкретном случае все достаточно просто.

В случае с регулярками алгоритм с откатами в худшем случае будет работать за экспоненциальное время, без откатов (обход вширь) — за O(l*n), ДКА будет работать за O(l) но надо будет потратить время на построение ДКА.

ЗЫ Извиняюсь за капитанство, выше tlp написал тоже самое, только без картинок