59
правок
Изменения
Нет описания правки
Для начала рассмотрим ситуацию, когда мы сравниваем наш образец с <tex>y[j \ldots j + m - 1]</tex>. Предположим, что первое несовпадение произойдет между <tex>x[i]</tex> и <tex>y[i + j]</tex> при <tex>0 < i < m</tex>. Тогда <tex>x[0 \ldots i - 1] {{=}} y[j \ldots i + j - 1] {{=}} u</tex> и <tex>a {{=}} x[i] \neq y[i + j] {{=}} b</tex>.
Когда сдвиг возможен, разумно ожидать, что префикс <tex>v</tex> шаблона совпадет c некоторым суффиксом <tex>u</tex>. Более того, если мы хотим избежать несовпадения при сдвиге, то нужно , чтобы символ, следующий за префиксом <tex>v</tex> в шаблоне, не совпадал с <tex>a</tex>. Такой наибольший префикс <tex>v</tex> называется '''помеченным бордером''' строки <tex>u</tex>.
{{Определение
