297
правок
Изменения
→Построение pm
==Построение pm==
Теперь осталось только обратиться к вычислению таблицы несовпадений шаблона на стадии предварительных вычислений. Не теряя общности, можно предположить, что <tex>m</tex> является некоторой степенью <tex>2</tex>. В алгоритме предварительной обработки используется разбиение множества <tex>{1, 2, ... , m-1}</tex> из <tex>m-1</tex> строк <tex>pm</tex> на следующие <tex>\log m</tex> подмножеств:
<tex>\{1\}, \{2, 3\}, \{4, 5, 6, 7\}, ... , \{m/2, ... , m-1\}</tex>
Алгоритм состоит из <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>.
==Оценка работы==
