Поиск подстроки в текстовом документе работает на основе алгоритмов, которые позволяют проверить, входит ли заданная подстрока в исходную строку и, если входит, найти первое вхождение. 1

Некоторые алгоритмы поиска подстроки:

• Прямой поиск (последовательный). 1 Суть алгоритма в посимвольном сравнении строки с подстрокой. 1 Сравнивают первый символ строки с первым символом подстроки, второй символ строки со вторым символом подстроки и так далее. 1 Если все символы совпали, фиксируется факт нахождения подстроки. 1 В противном случае подстроку сдвигают на одну позицию вправо и повторяют сравнение. 1
• Алгоритм Кнута, Морриса и Пратта. 1 Основан на том, что после частичного совпадения начальной части подстроки с соответствующими символами строки становится известна пройденная часть строки. 1 С помощью этих сведений можно быстро продвинуться по строке. 1
• Алгоритм Бойера — Мура. 25 Считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. 2 Сначала строят таблицу смещений для искомого образца. 2 Затем совмещают начало строки и образца и начинают проверку с последнего символа. 2 Если последний символ образца и соответствующий ему при наложении символ строки не совпадают, образец сдвигают на величину, полученную из таблицы смещений, и снова проводят сравнение. 2 Если символы совпадают, сравнивают предпоследний символ образца и так далее. 2 Поиск считается оконченным, когда все символы образца совпадают с наложенными символами строки. 2
• Алгоритм Рабина. 2 Выполняет линейный проход по строке и линейный проход по всему тексту. 2 Время работы алгоритма линейно зависит от размера строки и текста, программа работает быстро, так как проверяет только те подстроки, которые «напоминают» образец. 2