образец Р имеет размер n,
текст Т — размер m
Определение. Пусть М —
двоичный массив размером n х (m + 1), в котором
индекс i пробегает значения
от 1 до n, а индекс j — от 0 до m. Элемент
M(i, j) равен 1 в том и
только том случае, если первые i символов Р точно
совпадают с i символами Т,
кончаясь на позиции j. В противном случае
элемент равен нулю.
Например, если Т = California
и P=for, то
М(1,5) = M(2,6) = M(3,7) = 1,
тогда как для остальных комбинаций индексов
M(i, j) = 0. Существенно, что
элементы, равные 1, в строчке i показывают все ме-
ста в Г, где заканчиваются
копии Р[1..i], а столбец j показывает все префиксы Р,
которые заканчиваются в
позиции j строки Т.
Ясно, что М(n, j) = 1 в том и
только том случае, если вхождение Р заканчива-
ется в позиции j строки Г;
следовательно, вычисление последней строчки М реша-
ет задачу точного совпадения.
Чтобы вычислить М, алгоритм сначала создает для
каждого символа алфавита х
двоичный вектор U(x) длины n. U(x) полагается рав-
ным 1 в тех позициях Р9 где
стоит символ х. Например, если Р = abacdeab, то
U (а) = 10100010.
Определение. Определим
Bit-Shift(j) как вектор, полученный сдвигом век-
тора для столбца j вниз на
одну позицию и записью 1 в первой позиции.
Старое значение в позиции п
теряется. Иначе говоря, Bit-Shift(j) состоит из
единицы, к которой приписаны
первые п - 1 битов столбца j.
На рис. 4.1 показан столбец j
до и после этой операции.
0 0 10110110010110 – это
столбец
Рис. 4.1. Столбец j до и
после операции Bit-Shift(j)
4.2.1. Как построить массив М
Массив М вычисляется по
столбцам следующим образом. Нулевой столбец А/ весь
состоит из нулей. Элементы
любого другого столбца j' > 0 получаются из столб*
ца j — 1 и вектора U для
символа T(j). В частности, вектор для столбца j полу-
чается операцией побитового
логического умножения AND вектора Bit-Shift(j - 1)
и вектора U(T(j)). Более
формально, если мы обозначим через M(j) столбец /
матрицы М, то M(j) = Bit-Shift(j
- 1) AND U(T(j)). Например, если Р =
abaac
и Т = xabxabaaxa,
Когда восьмой столбец M
сдвигается вниз и логически умножается на U(a), мы
получаем
10010--столбец
что и является правильным
девятым столбцом М.
|