297
правок
Изменения
→Построение pm
Алгоритм состоит из <tex>\log m</tex> этапов. На этапе <tex>s</tex>, где <tex>1 < 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 - 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>, как в алгоритме анализа текста. {| border="0" |align="left" colspan="4"|<font size=2> pm[2^(h-1)...2^h-1][1...min(2^log(m-1)2k-1, m-2^(h))] = m+1 r = 2^(h-1) j = 2^(h-1) for i = 2^(h-1) to 2^h - 1 b = 0 if i < j merge(I, R, J, B) if b < min(2^log(m-1)2k-1, m-2^(h)) r = i extend(i, j, b)</font>|}
==Оценка работы==
