Изменения

Метод, используемый для вычисления этой таблицы, основан на методе, используемом на стадии анализа текста. Рассмотрим алгоритм для этапа <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>s - 1</tex> стадий. (Число элементов в строках подмассива будет объяснено позже). Выходы стадии <tex>s</tex> вводятся в //todopm. За исключением стадии <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>, как в алгоритме анализа текста.