Здравствуйте, tlp, Вы писали:

BZ>>конечный автомат будет делать ровно то же самое, что и обычное решение. просто это суперкомпиляция кода match() для конкретного паттерна. ну а учитывая, что паттерн и так представлен очень эффективной структурой данных — строкой — никакого выигрыша не будет вообще

tlp>Не понял, что такое "обычное решение". То, что тут приводили, работает за O(mn).

да, оно

tlp>Если автомат построить заранее, то он будет матчить строку за O(n).

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