Изменения

<tex>\{1\}, \{2, 3\}, \{4, 5, 6, 7\}, ... , \{m/2, ... , m-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>s - 1</tex> стадий. Выходы стадии <tex>s</tex> вводятся в <tex>pm</tex>. За исключением стадии <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>, как в алгоритме анализа текста.