Comments 8
Чтобы проверить, действительно ли эта статья про поиск, я вбил слово "поиск" в строку поиска, и оно нашлось аж целых 3 раза. Ну, видимо, это про поиск.
Вопрос: а для чего borderPositions в контексте статьи? Чтение английской статьи по ссылке тоже не дало ответов.
Для расчета prefixBorders
С помощью borderPositions во вкладке "Код получения массива сдвигов" вы можете посмотреть алгоритм
Спасибо за ответ, но
"Код получения массива сдвигов" вы можете посмотреть алгоритм
Там находится не алгоритм, а его реализация, конвертация реализации в алгоритм это определенная задача и навыки, я пока осилить это не смог, так как не могу связать код с текстом статьи, поэтому и появился вопрос.
Если обращаться к коду английской версии статьи, то там написано в разных местах много про границы (borders):
/*if character at position i-1 is not
equivalent to character at j-1, then
continue searching to right of the
pattern for border */
но не могу найти что это за границы и как именно используются.
Не граница, а грань. Это некоторый суффикс строки, который равен ее префиксу. Подробнее про их полезность вы можете прочитать в предыдущей статье:)
Вообще здесь не совсем классические грани, а грани префиксов. Они нужны для более жадных переносов. Т.Е. когда у нас не сходятся проверяемые символы, то мы не просто переносим индекс поиска, а к следующему вхождению подобного паттерна.
Не граница, а грань
border [ˈbɔːdə] сущ
граница ж, край м, кайма ж, рубеж м, предел м, грань ж
синонимично же, не принципиально
Это некоторый суффикс строки, который равен ее префиксу. Подробнее про их полезность вы можете прочитать в предыдущей статье:)
Как раз не мог понять долго что именно это, у вас во многих местах понятия строка, подстрока, паттерн и т.п. перемешиваются друг с другом. Изначально считал что речь сугубо про префиксы и суффиксы паттерна (подстроки, искомого образца). Но пока ждал ваш ответ еще читал всякое на эту тему и пришло озарение, что речь про префиксы и суффиксы кусочков паттерна увеличивающихся на 1, то есть для подстроки cosmos это:
c
co
cos
cosm
cosmo
cosmos
И для каждого считает размер префикса/суффикса.
Будем считать что какое-то понимает достигнуто.
то мы не просто переносим индекс поиска, а к следующему вхождению подобного паттерна.
Саму идею понимаю, весьма интересно. Пишу свою реализацию в виде сборной солянки разных алгоритмов, чисто спортивный интерес. Например здесь:
находится совпадение за 2 шага из-за отсутствия символов "c" и "d" в подстроке, о чём вы написали уже в следующей статье. В общем интересно сделать что-то заковыристое. Спасибо вам за статьи. ????
Строковые алгоритмы на практике. Часть 2 — Алгоритм Бойера — Мура