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

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

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

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

BZ>да, оно

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

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

Без бэктрекинга — двухмерное ДП =) вроде уже писал, но O(nm).