Изменения

Префикс-функция от строки <tex>S</tex> строится за <tex>O(S) = O(P + T)</tex>. Проход цикла по строке <tex>S</tex> содержит <tex>O(T)</tex> итераций. Итого, время работы алгоритма оценивается как <tex>O(P + T)</tex>. Если мы хотим произвести множественный поиск образцов в тексте, то необходимо построить префикс-функцию для каждого из образцов в отдельности, тогда, учитывая, что длина образца обычно много меньше, чем длина текста, то общее время работы оценивается как <tex>O(mT)</tex>, где <tex>m</tex>{{---}} количество образцов.