Изменения
Нет описания правки
Нам даны: <tex>y</tex> {{---}} текст, <tex>x</tex> {{---}} образец, <tex>m = |x|</tex>, <tex>n = |y|</tex>.
Для начала рассмотрим ситуацию, когда мы сравниваем наш образец с <tex>y[j \ldots j + m - 1]</tex>. Предположим, что первое несовпадение произойдет между <tex>x[i]</tex> и <tex>\neq 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>.
