Изменения

Перейти к: навигация, поиск

Алгоритм Ландау-Вишкина (k несовпадений)

1 байт добавлено, 22:23, 16 июня 2014
Построение pm
<tex>\{1\}, \{2, 3\}, \{4, 5, 6, 7\}, ... , \{m/2, ... , m-1\}</tex>
Алгоритм состоит из <tex>\log m</tex> этапов. На этапе <tex>s</tex>, где <tex>1 \leqslant s < \log m</tex>, вычисляются строки <tex>pm</tex> в множестве <tex>s</tex>, где множество <tex>s</tex> {{---}} это <tex>\{2^{s-1}, ... , 2^{s}-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>, как в алгоритме анализа текста.
297
правок

Навигация