Изменения

Докажем, что метод <tex>Shift\texttt{-}And</tex> правильно вычисляет элементы массива <tex>M</tex>. Заметим, что для любого <tex>i > 1</tex> элемент <tex>M[i][j] = 1</tex> тогда и только тогда, когда <tex>p[1..i - 1]</tex> совпадает с <tex>t[j - i + 1 \dots .. j-1]</tex>, а символ <tex>p[i]</tex> совпадает с <tex>t[j]</tex>. Первое условие выполнено, когда элемент массива <tex>M[i - 1][j - 1] = 1</tex>, а второе — когда <tex>i</tex>-ый бит вектора <tex>U</tex> для символа <tex>t[j]</tex> равен <tex>1</tex>. После сдвига столбца Таким образом, чтобы вычислить элемент <tex>M[i][j - 1] </tex>, нужно взять результат побитовой операции <tex> and </tex> алгоритм логически умножает элемент элементов <tex>M[i - 1][j - 1]</tex> столбца и <tex>U[t[j]][i]</tex>. Это эквивалентно применению побитовой операции <tex> and </tex> к вектору <tex> U[t[j]] </tex> и сдвинутому на <tex> 1 </tex> столбцу под номером <tex>j - 1</tex> на элемент массива <tex> M </tex>. Для <tex>i= 1 </tex> вектора нам достаточно проверить, что <tex>U([t[j])][1] = 1 </tex>. Следовательно, все элементы поэтому мы и записываем в <tex>M[1][j] </tex> вычисляются правильно единицу, что и делает операция <tex> Bit\texttt{-}Shift </tex>. Получаем, что наш алгоритм находит корректно вычисляет все вхождения образца в текстзначения массива <tex> M </tex>.