Изменения

В 1990ые годы Рикардо Беза-Йетс (англ. ''Ricardo Baeza-Yates'') и Гастон Гоннет (англ. ''Gaston Gonnet'') изобрели простой битовый метод, эффективно решающий задачу точного поиска малых образцов (длиной в типичное английское слово). Они назвали его методом <tex>Shift-Or</tex>, хотя, исходя из самого алгоритма, естественней назвать его <tex>Shift-And</tex>. Также алгоритм известен как <tex>bitap </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>Shift-Or </tex> правильно вычисляет элементы массива <tex>M</tex>. Заметим, что для любого I <tex>i > 1</tex> элемент <tex> 1элемент M([i, ][j) ] = 1 т </tex> тогда и тттолько тогда, когда <tex>p[1..i – 1] </tex> совпадает с <tex>t[j – i + 1..j]</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>j – 1 </tex> алгоритм логически умножает элемент <tex>M([i – 1, ][j – 1) ]</tex> столбца <tex>j – 1 </tex> на элемент <tex>i </tex> вектора <tex>U(t[j])</tex>. Следовательно, все элементы <tex>M </tex> вычисляются правильно и алгоритм находит все вхождения образца в текст.

Сложность алгоритма составляет <tex>O(nm)</tex>, на препроцессинг — построение массива <tex>U </tex> требуется <tex>O(сигма*n) </tex> операций и памяти. Если же <tex>n </tex> не превышает длину машинного слова, то сложность получается <tex>O(m) </tex> и <tex>O(n + сигма) </tex> соответсвенно.