418
правок
Изменения
Нет описания правки
* <tex>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 : Cs(i, s) \ and \ Co(i, s)\}</tex>. А значение <tex>bmGs[0]</tex> определим, как длину периода шаблона <tex>x</tex>.
Для вычисления bmGs будем использовать таблицу <tex>suff</tex>, определенную так:
для всех <tex>i</tex> таких, что <tex>1 \leqslant i < m</tex> выполняется <tex>suff[i]=\max\{k : x[i-k+1 .. i]=x[m-k .. m-1]\}</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\ x[m-1-i]=c\}, & \mbox{if } c \in x\\
m, & \mbox{otherwise}
\end{cases}</tex>
==Псевдо-код==
