Казалось бы, что может быть сложного в поиске чего то в тексте? В любом текстовом редакторе, браузере, pdf-читалке просто вводишь нужное тебе слово и оно находится в тексте.
Но что если наши запросы стали расти и нужно найти что то более нетривиальное? Я бы хотел рассказать о такой... иерархии видов поиска, от простых до более сложных. И конкретно в этой статье я начну с простого поиска в строке.
Простой поиск одного слова в строке
Начнем с самого простого, есть строка "рыжий кот поймал мышь", и мы должны найти в нем слово "кот". Как это реализовать? Возьмем самый простой способ. Длина слова "кот" - 3 символа. Теперь мы идем по строке начиная с первого символа, и начиная с этого текущего символа берем три символа. получается "рыж". Сравниваем это со словом "кот", и если не совпало то идем дальше: "ыжи", "жий", "ий " и т.д. В итоге мы придем к слову "кот". У нас был счетчик равный нулю, и при каждой попытке мы увеличивали его на единицу, и поэтому мы знаем что слово "кот" находится на 7-ой позиции считая слева.
Этот алгоритм медленный поэтому есть более оптимизированные варианты, например, наверно самый популярный алгоритм - алгоритм Кнута-Морриса-Пратта (KMP).
Алгоритм Кнута-Морриса-Пратта (KMP)
Возьмем строку "кот поймал мышь" и добавим к ней в начало строку "кот", которую мы ищем, причем между этими двумя кусками текста поставим символ-разделитель % которого нет в наших двух строках. Получается "кот%кот поймал мышь".
Теперь к этой строке надо применить так называемую "префикс-функцию". Возьмем первые три символа из этой строки и составим такую таблицу, где сверху вниз идут символы, номера символов по порядку и в самом низу особая строка которую надо заполнить по определенным правилам. В первую ячейку этой строки под первым символом сразу записываем 0.
Берем первый символ в начале строки "ко" и последний. Получается "к" и "о". Под буквой "о" надо записать сколько совпадений мы нашли между строками "к" и "о". Ну тут если они одинаковые значит будет 1, но у нас "к" и "о" это разные буквы, поэтому будет 0.
Добавим еще одну букву.
Теперь так же проверим первый и последний символы, "к" и "т". Они разные. Тогда берем первые и последние два символа "ко" и "от". Они тоже разные. Значит совпадений нет, и мы снова ставим 0.
И так это будет продолжаться до этого момента:
Проверим первый и последний символы "к" и "т". Они разные. Тогда первый и последние два символа "ко" и "от". Они тоже разные. Возьмем три символа "кот" и "кот". Наконец то! Совпадение! Раз мы брали по 3 символа, то и число ставим 3. Если бы совпадение было на 2 символах то поставили бы 2, если на одном то 1. Потом возьмем еще так же по 4 символа, по 5, и так до 6. Семь символов уже не берем. Если бы совпадение было на больших числах например на 4, то мы бы уже написали не 3 а 4.
До конца строки дальше уже будут одни нули.
В слове "кот" три символа. Ищем в этом нашем новом массиве число 3, и оно стоит на 7 по счету символе. Этот индекс 7 будет указывать на конец нашего слова которые мы искали. Таким образом слово найдено. Но проблема в том что чем дальше мы заходим тем сильнее растет количество проверок. Чтоб ускорить все это дело есть разные оптимизации. Например мы можем брать сначала не по одному символу, потом по два и т.д. а наоборот, сначала допустим по 7 символов, потом по 6 и т.д. Либо мы можем идти в обратную сторону не по порядку а переходить к тому символу номер которого равен числу записанному под предыдущим символом в нашем новом массиве. После всех оптимизаций алгоритм начинает работать быстрее предыдущего простого алгоритма.