T>Да, о реализации движков очень хорошо изложено в классической книжке «Регулярные выражения» Дж. Фридла, глава 4.
T>Там же описаны гибридные реализации. Например можно строить для регулярки ДКА (игнорируя некоторые навороты) и НКА. Далее ищем по строке с помощью ДКА, а имея совпадение прогоняем на нём НКА.
T>К сожалению, о ТДКА Фридл ни во втором, ни в 3-ем русском издании не упоминает.

Ещё неплохо почитать до сих пор актуальные статьи от Russ Cox: https://swtch.com/~rsc/regexp/
Он же написал RE2, которая в данном случае должна отрабатывать линейно, если мне склероз не изменяет. RE2 тоже не панацея, в некоторых случаях откатывается на реализацию с бэктрекингом.