Изменения

Алгоритм состоит из <tex>\log m</tex> этапов. На этапе <tex>s</tex>, где <tex>1 < \leqslant s < \log m</tex>, вычисляются строки <tex>pm</tex> в множестве <tex>s</tex>, где множество <tex>s</tex> – это <tex>{2s-1, ... , 2s-1}</tex>.

Метод, используемый для вычисления этой таблицы, основан на методе, используемом на стадии анализа текста. Рассмотрим алгоритм для этапа <tex>s</tex>. На стадии <tex>s</tex> входами для алгоритма анализа образца являются подстроки образца <tex>x[1...m-2^{s-1}]</tex> и <tex>x[2^{s-1}+1...m]</tex>, которые трактуются здесь, соответственно, как образец и текст, и массив <tex>pm[1...2^({s-1)}-1][1...min\{2^{log(m)-s}4k+1, m-2^{s-1}\}]</tex>, содержащий выходы предыдущих <tex>l s - 1</tex> стадий. (Число элементов в строках подмассива будет объяснено позже). Выходы стадии <tex>s</tex> вводятся в //todo. За исключением стадии <tex>\log m</tex>, на которой находят до <tex>2k+1</tex> несовпадений, на стадии <tex>s</tex> для каждой строки <tex>pm</tex> требуется найти до <tex>min\{2^{log(m)-s}2k+1, m-2^{s}\}</tex> несовпадений, а не до <tex>k+1</tex>, как в алгоритме анализа текста.

pm[<tex>2^({h-1)}</tex>...<tex>2^h{s-1}</tex>][1...min({<tex>2^{\log(m-1)}2k-1</tex>, <tex>m-2^(h)){s}</tex>}] = m+1 r = <tex>2^(h{s-1)}</tex> j = <tex>2^(h{s-1)}</tex> for i = <tex>2^(h{s-1) }</tex> to <tex>2^h {s} - 1</tex> b = 0 if i < j merge(I, R, J, B) if b < min({<tex>2^{log(m-1)}2k-1, m-2^(h)){s} </tex>} r = i extend(i, j, b)