Изменения

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

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

243 байта добавлено, 21:52, 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> {{---}} суммарное время построения префикс-функций для всех образцов.
==Оценка по памяти==
Анонимный участник

Навигация