Изменения

Нам потребуется двоичный массив <tex>M</tex> размером <tex>n \cdot times (m + 1)</tex>, в котором индекс <tex>i</tex> пробегает значения от <tex>1</tex> до <tex>n</tex>, а индекс <tex>j</tex> {{---}} от <tex>0</tex> до <tex>m</tex>.

1, & \mbox {if p[1..$\ldots$ i] = t[j - i + 1..$\ldots$ j]} \\

Получаем, что элементы, равные <tex>1</tex>, в строчке <tex>i</tex> показывают все места в <tex>t</tex>, где заканчиватся копии <tex>p[1..\ldots i]</tex>, а столбец <tex>j</tex> показывает все префиксы <tex>p</tex>, которые заканчиваются в позиции <tex>j</tex> строки <tex>t</tex>.

'''string''' bitap_searchshiftAndSearch('''string''' text, '''string''' pattern):

M = new array [n] of bit <font color=green> // для поиска коротких слов достаточно одной переменной типа '''integer''' </font>

U = new array [<tex>|\Sigma|</tex>][n] of bit, initially all <font color=green> // изначально все элементы равны <tex> 0</tex> </font> '''for''' i = 1..n <font color=green> // препроцессинг {{- --}} вычисление вектора <tex> U</tex> </font>

Докажем, что метод <tex>Shift\texttt{-}And</tex> правильно вычисляет элементы массива <tex>M</tex>. Заметим, что для любого <tex>i > 1</tex> элемент <tex>M[i][j] = 1</tex> тогда и только тогда, когда <tex>p[1..\ldots i - 1]</tex> совпадает с <tex> t[j - i + 1 .. \ldots 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] </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>.

Сложность алгоритма составляет <tex>O(n \cdot m)</tex>, на препроцессинг {{---}} построение массива <tex>U</tex> {{---}} требуется <tex>O(|\Sigma| \cdot n)</tex> операций и памяти. Если же <tex>n</tex> не превышает длину машинного слова, то сложность получается <tex>O(m)</tex> и <tex>O(n + |\Sigma|)</tex> соответсвенно.

Аналогичен алгоритму <tex>Shift\texttt{-}And</tex>, но вместо массива <tex>M</tex> используется массив <tex>R</tex>, определяемый следующим образом:

0, & \mbox {if p[1..$\ldots$ i] = t[j - i + 1..$\ldots$ j]} \\

Следующий столбец <tex>R[j]</tex> получается операцией побитового логического сложения <tex>or</tex> вектора <tex>Bit\texttt{-}Shift'(R[j - 1])</tex> и вектора <tex>W([t[j])]</tex>. Здесь <tex>W([t[j]) ] = not \ U([t[j])]</tex>, а <tex>Bit\texttt{-}Shift'(R[j - 1])</tex> {{--- }} сдвиг вектора <tex>R[j - 1]</tex> на одну позицию вниз с записью <tex>0</tex> в первой позиции.

<tex>R[j] = Bit\texttt{-}Shift'(R[j - 1]) \ or \ W([t[j])]</tex>

Очевидно, что алгоритм <tex>Shift\texttt{-}Or</tex> корректен, так как данная формула получается применением логического отрицания к аналогичной формуле для алгоритма <tex>Shift\texttt{-}And</tex>, корректность которого была доказана выше.