Изменения

Пусть <tex>p </tex> – шаблон длины <tex>n</tex>, <tex>t </tex> – текст длины <tex>m</tex>.

Нам потребуется двоичный массив <tex>M </tex> размером <tex>n * (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>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>, в строчке I <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>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>Bit-Shift(j) </tex> как вектор, полученный сдвигом вектора для столбца <tex>j </tex> вниз на одну позицию и записью <tex>1 </tex> в первой позиции. Старое значение в позиции <tex>n </tex> теряется. То есть <tex>Bit-Shift(j) </tex> состоит из <tex>1</tex>, к которой приписаны первые <tex>n – 1 </tex> битов столбца <tex>j</tex>.<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) → (1, 0, 0, 1, 0, 1, 1, 0)</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>