Изменения

Перейти к: навигация, поиск

Алгоритм Кнута-Морриса-Пратта

813 байт убрано, 22:07, 30 мая 2014
Нет описания правки
answer[count++] = i + 1 - p
'''return''' answer
 
==Множественный поиск образцов==
Если мы хотим произвести множественный поиск образцов в тексте, то для начала построим префикс-функции для всех образцов, а затем, при проходе по символам текста, будем сразу подсчитывать префикс-функции для каждого образца.
==Время работы==
Префикс-функция от строки <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> {{---}} суммарное время построения префикс-функций для всех образцов.
==Оценка по памяти==

Навигация