Какова сложность этого детерминированного алгоритма КМП на основе конечных автоматов?Является ли он более эффективным, чем стандартная, неавтоматическая версия алгоритма KMP?
Я считаю, что стандартная версия KMP более эффективна, поскольку использует меньше памяти, чем версия DFA. Массив DFA может стать довольно большим, если у вас большой алфавит и большой шаблон.
Реализация обеих версий может быть найдена в текущих ссылках с довольно хорошей документацией о том, как они работают на соответствующих страницах курса (обратите внимание, что в данных ссылках KMPplus является стандартной версией).
http://algs4.cs.princeton.edu/53substring/KMP.java.html http://algs4.cs.princeton.edu/53substring/KMPplus.java.html