177
правок
Изменения
м
→Алгоритм
Алфавит обозначим буквой <tex>\Sigma</tex>.
Пусть <tex>|y|=n</tex>, <tex>|x|=m</tex> и <tex>|\Sigma|=\sigma</tex>.
Предположим, что в процессе сравнения возникает несовпадение между символом <tex>x[i]=a</tex> шаблона и символом <tex>y[i+j]=b</tex> исходного текста при проверке в позиции <tex>j</tex>. Тогда <tex>x[i+1 \dots m-1]=y[i+j+1 \dots j+m-1]=u</tex> и <tex>x[i] \neq y[i+j]</tex>, и <tex>m - i - 1</tex> символов шаблона уже совпало.
