Изменения

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

Алгоритм Бойера-Мура

6 байт добавлено, 15:26, 3 мая 2016
Формальное определение
* <tex>\mathrm{Co}(i, s)</tex>: если <tex>s < i</tex>, то выполняется <tex>x[i-s] \neq x[i]</tex>
Тогда для всех <tex>i</tex> таких, что <tex>0 \leqslant i < m</tex> выполняется <tex>bmGs[i+1]=\min\{s > 0 : \mathrm{Cs}(i, s)\ and\wedge\ \mathrm{Co}(i, s)\}</tex>.
А значение <tex>bmGs[0]</tex> определим, как длину периода шаблона <tex>x</tex>.
Сдвиги плохих символов будем хранить в массиве <tex>bmBc</tex> размером <tex>\sigma</tex>.
Для каждого символа <tex>c</tex> из <tex>\Sigma</tex>: <tex>bmBc[c] = \begin{cases}
\min\{i : 1 \leqslant i < m-1\ and\wedge\ x[m-1-i]=c\}, & \mbox{if } c \in x\\
m, & \mbox{otherwise}
\end{cases}</tex>
Анонимный участник

Навигация