Изменения

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