1
правка
Изменения
м
Исправление ошибок с отображением \ldots, замена \cdot на \times при указании размера массива
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.
Нам потребуется двоичный массив <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>.
<tex>M[i][j] = 1</tex>, если первые <tex>i</tex> символов <tex>p</tex> точно совпадают с <tex>i</tex> символами <tex>t</tex>, кончаясь на позиции <tex>j</tex>; иначе <tex>M[i][j] = 0</tex>.
\left\{
\begin{array}{ll}
1, & \mbox {if p[1..$\ldots$ i] = t[j - i + 1..$\ldots$ j]} \\
0, & \mbox {otherwise}
\end{array}
Например, пусть <tex>t = california</tex>, <tex>p = for</tex>. Тогда <tex>M[1][5] = M[2][6] = M[3][7] = 1</tex>, остальные <tex>M[i][j] = 0</tex>.
Получаем, что элементы, равные <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>.
<tex>M[n][j] = 1</tex> тогда, когда вхождение <tex>p</tex> заканчивается в позиции <tex>j</tex> строки <tex>t</tex>.
==Корректность==
Докажем, что метод <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>.
==Эффективность==
\left\{
\begin{array}{ll}
0, & \mbox {if p[1..$\ldots$ i] = t[j - i + 1..$\ldots$ j]} \\
1, & \mbox {otherwise}
\end{array}
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Поиск подстроки в строке]]
[[Категория: Точный поиск]]
