Изменения

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

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

36 байт добавлено, 18:10, 11 мая 2014
м
Формальное определение
Определим два условия:
* <tex>\mathrm{Cs}(i, s)</tex>: для каждого <tex>k</tex> такого, что <tex>i < k < m</tex> выполняется <tex>s \geqslant k</tex> или <tex>x[k-s]=x[k]</tex>* <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\ \mathrm{Co}(i, s)\}</tex>. А значение <tex>bmGs[0]</tex> определим, как длину периода шаблона <tex>x</tex>.
Для вычисления bmGs будем использовать функцию <tex>\mathrm{suffixLength}</tex>, определенную так:
418
правок

Навигация