Изменения
Нет описания правки
Пусть <tex>p</tex> {{---}} шаблон длины <tex>n</tex>, <tex>t</tex> {{---}} текст длины <tex>m</tex>.
Нам потребуется двоичный массив <tex>M</tex> размером <tex>n * \cdot (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] =</tex> \{ <tex>1</tex>, если первые <tex>i</tex> символов <tex>p</tex> точно совпадают с <tex>i</tex> символами <tex>t</tex>, кончаясь на позиции <tex>j</tex>; <tex>0</tex> {{---}} иначе<tex>\}</tex>.
То есть <tex>M[i][j] = 1</tex> тогда и только тогда, когда <tex>p[1..i] = t[j - i + 1..j]</tex>.
Например, пусть <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..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>M</tex>.
Создадим для каждого символа алфавита <tex>x</tex> двоичный вектор <tex>U(x)</tex> длины <tex>n</tex>. <tex>U(x)</tex> равно <tex>1</tex> в тех позициях <tex>p</tex>, где стоит символ <tex>x</tex>.
Например, <tex>p = abacdeab</tex>, <tex>U(a) = 10100010</tex>
Из определения, нулевой столбец <tex>M</tex> состоит из нулей. Элементы любого другого столбца <tex>j > 0</tex> получаются из столбца <tex>j - 1</tex> и вектора <tex>U</tex> для символа <tex>t[j]</tex>. А именно, вектор для столбца <tex>j</tex> получается операцией побитового логического умножения <tex>and</tex> вектора <tex>Bit-Shift(j - 1)</tex> и вектора <tex>U(t[j])</tex>.
<tex>M[j] = Bit-Shift(j - 1) and U(t[j])</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> соответсвенно.
