Аннотация:В работе Спиркина Р.О. рассматриваются особенности нахождения префикс функция строки, рассмотрено несколько методов решения этой задачи. Приведен наиболее быстрый способ из рассмотренных, доказана его асимптотика. Приведены несколько возможных сценариев применения полученных результатов поиска подстроки в тексте.
В работе за основу взят стандартный переборный алгоритм, формулируются и обсуждаются два замечания, позволяющие его улучшить. Описывается итоговый алгоритм и его реализация. Кратко обсуждаются возможные приложения полученных результатов.