Изменения

Перейти к: навигация, поиск

Алгоритм Shift-Or

187 байт добавлено, 22:02, 7 июня 2014
Нет описания правки
<tex>(0, 0, 0, 1, 0, 1, 1, 0, 1) \rightarrow (1, 0, 0, 1, 0, 1, 1, 0)</tex>
Из определения, нулевой столбец <tex>M</tex> состоит из нулей. Элементы любого другого столбца <tex>M[j], j > 0</tex> получаются из столбца <tex>M[j - 1]</tex> и вектора <tex>U</tex> для символа <tex>t[j]</tex>. А именно, вектор для столбца <tex>j</tex> получается операцией побитового логического умножения <tex>and</tex> вектора <tex>Bit-Shift(M[j - 1])</tex> и вектора <tex>U(t[j])</tex>. <tex>M[j] = Bit-Shift(M[j - 1]) and U(t[j])</tex>
Например, …
==Псевдокод==
'''string ''' bitap_search('''string ''' text, '''string ''' pattern) n = |pattern| m = |length(pattern)| '''if m ''' n == 0 '''return ''' text M := new array[n][m+1] of bit, initially all 0 MU = new array [<tex>|\Sigma|</tex>][n] of bit, initially all 0] = 1 '''for ''' i = 01..length(text)n U[pattern[i]][i] = 1 M[0][i] = 0 '''for k ''' j = m1..1 /* Update the bit array. */m M[kj] = Bit-Shift(M[k j - 1] & (text) '''and''' U[t[ij]] '''for''' j == pattern[k - 1])..m '''if ''' M[mn][j]: '''return (''' text + i [j - m) n + 1..j] '''return ''' null
==Корректность==
Анонимный участник

Навигация