Слайды лекций - 2014 (лектор - Белеванцев А. А.) (1107979), страница 12

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

Зная k (число символов,заведомо совпадающих при проверке нового сдвига s′), можновычислить s′ по формуле s′ = s + (q – k).7Алгоритм Кнута – Морриса – Пратта. Префикс-функцияОпределение. Префикс-функцией, ассоциированной со строкойP[1..m], называется функция π: {1,2, …, m} → {0,1, …, m – 1},определенная следующим образом:π[q] = max{k: k<q & Pk  Pq }Иными словами, π[q] – длина наибольшего префикса P,являющегося суффиксом Pq.8Алгоритм Кнута – Морриса – Пратта. Префикс-функцияvoid prefix_func (char *pat, int *pi, int m) {int k, q;/* Считаем, что pat и pi нумеруются от 1 */pi[1] = 0; k = 0;for (q = 2; q <= m; q++) {while (k > 0 && pat[k + 1] != pat[q])k = pi[k];if (pat[k + 1] == pat[q])k++;pi[q] = k;}}9Алгоритм Кнута – Морриса – Пратта. Префикс-функцияЛемма 1.

Обозначим π * [ q] = {q, π [ q], π 2 [ q],..., π t [ q]},где π i [q] есть i-я итерация префикс-функции, π t [ q] = 0.Пусть P – строка длины m c префикс-функцией π.Тогда для всех q = 1, 2, ..., m имеем π * [ q] = {k :Pk  Pq }.Лемма показывает, что при помощи итерированияпрефикс-функции можно для данного q найти все такие k, чтоPk является суффиксом Pq.Доказательство.(1)Покажем, что если i принадлежит π*[q], то Pi являетсясуффиксом Pq.Действительно, Pπ [ i ]  Pi по определению префиксфункции, так что каждый следующий членпоследовательности Pi , Pπ [ i ] , Pπ [π [ i ]] ,...

являетсясуффиксом всех предыдущих.10Алгоритм Кнута – Морриса – Пратта. Префикс-функцияДоказательство.(2)Покажем, что наоборот, если Pi является суффиксом Pq,то i принадлежит π*[q].Расположим все Pi , являющиеся суффиксами Pq, впорядке уменьшения i (длины): Pi1, Pi2,…Покажем по индукции, что Pik = πk[q].База индукции (k=1): для максимального префикса Pi ,являющегося суффиксом Pq, по определению i=π[q].Шаг индукции: если Pik = πk[q], то по определениюj = π[πk[q]] соответствует максимальный префикс Pj,который является суффиксом Pik.

Обе строки Pj и Pikесть суффиксы Pq по построению. Таким максимальнымпрефиксом из оставшихся Pik+1, Pik+2,… по построениюявляется префикс Pik+1 ,то есть j = ik+1.(2) можно доказать и от противного: для наибольшегочисла j такого, что Pj  Pq , но j не входит в π*[q],определение префикс-функции нарушается.11Алгоритм Кнута – Морриса – Пратта. Префикс-функцияπ [8] = {8,6,4,2,0}*12Алгоритм Кнута – Морриса – Пратта.

Префикс-функцияЛемма 2. Пусть P – строка длины m c префикс-функцией π.Тогда для всех q = 1, 2, ..., m, для которых π [ q] > 0 ,*имеем π [ q ] − 1 ∈ π [ q − 1] .Доказательство.Если k = π [ q ] > 0 , то Pk является суффиксом Pqпо определению префикс-функции.Следовательно, Pk-1 является суффиксом Pq-1.Тогда по Лемме 1 k − 1 ∈ π * [ q − 1] , т.е.π [q] − 1 ∈ π *[q − 1] .Определим множества Eq-1 какEq −1 = {k : k ∈ π *[ q − 1] и P[k + 1] = P[ q]}.Множество Eq-1 состоит из таких k, что Pk является суффиксомPq-1, и за ними идут одинаковые буквы P[k+1] и P[q].Из определения вытекает, что Pk+1 есть суффикс Pq.13Алгоритм Кнута – Морриса – Пратта.

Префикс-функцияСледствие 1. Пусть P – строка длины m c префикс-функцией π.Тогда для всех q = 2, 3, ..., m0, если Eq −1 пусто;π [q] = 1 + max{k ∈ Eq −1}, если Eq −1 не пусто.Доказательство.Если r = π [ q] ≥ 1 , то P[r] = P[q] и по Лемме 2r − 1 = π [ q] − 1 ∈ π *[ q − 1] .Т.к. P[r] = P[q], то P[(r-1)+1] = P[q].Поэтому r − 1 ∈ Eq −1 по определению Eq-1 и из π [ q] ≥ 1следует непустота Eq-1.Следовательно, если Eq-1 пусто, то π [ q] = 0 (от противного).Если k ∈ Eq −1 , то Pk+1 есть суффикс Pq (из определения),следовательно,π [ q ] ≥ k + 1 и π [ q] ≥ 1 + max{k ∈ Eq −1}.То есть, если Eq-1 не пусто, то префикс-функцияположительна. Но тогдаπ [ q] − 1 ∈ Eq −1 , π [ q] − 1 не большемаксимума из Eq-1, т.е. π [ q] ≤ 1 + max{k ∈ Eq −1}.14Алгоритм Кнута – Морриса – Пратта. Префикс-функция1 void prefix_func (char *pat, int *pi, int m) {2int k, q;34/* Считаем, что pat и pi нумеруются от 1 */5pi[1] = 0; k = 0;6for (q = 2; q <= m; q++) {7while (k > 0 && pat[k + 1] != pat[q])8k = pi[k];9if (pat[k + 1] == pat[q])10k++;11pi[q] = k;12}13 }15Алгоритм Кнута – Морриса – Пратта.

Префикс-функцияТеорема 1. Функция prefix_func правильно вычисляетпрефикс-функцию π.Доказательство.Покажем, что при входе в цикл функции k = π[q-1].База индукции.При q = 2 k = 0, pi[q-1] = pi[1] = 0.Шаг индукции.Пусть при входе в цикл функции k = π[q-1].Код на строках 7-8while (k > 0 && pat[k + 1] != pat[q])k = pi[k];находит наибольший элемент Eq-1 (т.к. цикл перебираетв порядке убывания элементы из π*[q-1] и для каждогопроверяет равенство pat[k + 1] != pat[q])).16Алгоритм Кнута – Морриса – Пратта. Префикс-функцияТеорема 1. Функция prefix_func правильно вычисляетпрефикс-функцию π.Доказательство.После выхода из цикла на строках 7-8while (k > 0 && pat[k + 1] != pat[q])k = pi[k];1) если pat[k + 1] == pat[q], то выполняется код настроке 10:k++;что из Следствия 1 дает нам π[q].2) если pat[k + 1] != pat[q], то k == 0,множество Eq-1 пусто и π[q] = 0.17Алгоритм Кнута – Морриса – Пратта. Функция kmpvoid kmp (char *text, char *pat, int m, int n) {int q;int pi[m + 1]; /* VLA-массив *//* Через alloca: int *pi = alloca ((m + 1) * sizeof (int)); *//* Считаем, что pat и text нумеруются от 1 */prefix_func (pat, pi, m);q = 0;for (i = 1; i <= n; i++) {while (q > 0 && pat[q + 1] != text[i])q = pi[q];if (pat[q + 1] == text[i])q++;if (q == m) {printf ("образец входит со сдвигом %d\n", i – m);q = pi[q];}18}Алгоритм Кнута – Морриса – Пратта.

Функция kmpАлгоритм КМП для подстроки P и текста Т эквивалентенвычислению префикс-функции для строки Q = P#T, где# – символ, заведомо не встречающийся в обеих строкахДлина максимального префикса Q, являющегося еёсуффиксом (т.е. значение префикс-функции),не превосходит длины PДопустимый сдвиг обнаруживается в тот момент, когдаочередное вычисленное значение префикс-функциисовпадает с длиной подстроки P (условие if (q == m))В явном виде объединенная строка не строится!Теорема 2. Функция kmp работает правильно.Формальное доказательство осуществляется по аналогиис доказательством Теоремы 1, где множества, подобныеEq-1, строятся для строки-текста, а не строки-образца.Свойства префикс-функции часто используются и в другихзадачах (кроме поиска подстроки в строке)Полезной оказывается Лемма 1: итерированиемпрефикс-функции можно найти все префиксы строки, 19являющиеся ее суффиксамиАлгоритм Кнута – Морриса – Пратта.

Время работыФункция prefix_func выполняет ≤ (m – 1) итераций цикла for.Стоимость каждой итерации можно считать равной O(1),а стоимость всей процедуры O(m).Каждая итерация цикла while (строки 7-8) уменьшает kУвеличивается k только в строке 10 не более одного разана итерацию цикла for (строки 6-11)Следовательно, операций уменьшения не больше, чемитераций цикла for, то есть ≤ (m – 1) на весь цикл иO(1) на итерацию в среднемАналогично, функция kmp выполняет ≤ (n – 1) итераций, и еестоимость (без учета вызова prefix_func) есть O(n).Следовательно, время выполнения всей процедуры O(m + n).20Курс «Алгоритмы и алгоритмические языки»1 семестр 2014/2015Лекция 191Двоичное деревоДвоичное дерево – набор узлов, который:либо пуст (пустое дерево),либо разбит на три непересекающиеся части:узел, называемый корнем,двоичное дерево, называемое левым поддеревом, идвоичное дерево, называемое правым поддеревом.Двоичное дерево не является частным случаем обычногодерева, хотя у этих структур много общего.

Основные отличия:(1)Пустое дерево является двоичным деревом, но неявляется обычным деревом.(2)Двоичные деревья (A(B,NULL)) и (A(NULL,B))различны, а обычные деревья – одинаковы.Термины: узлы, ветви, корень, листья, высота2Двоичное деревоПредставление двоичного дерева в памяти компьютераОписание узла двоичного дерева на Си:typedef struct bin_tree {char info;struct bin_tree *left;struct bin_tree *right;} node;3Двоичное деревоОбход двоичного дерева.Обход дерева позволяет выполнить топологическую сортировкуузлов дерева и расположить их в линейном одномерноммассиве, порядок узлов дерева в котором таков, что их можнообрабатывать в циклеfor (i = 0; i < N; i++)(топологический порядок)4Двоичное деревоРазличные способы обхода двоичного дерева(1)Обход в глубину в прямом порядке:обработать корень,обойти левое поддерево,обойти правое поддерево.Порядок обработки узлов дерева на рисункеA B D C E G F H JЛинейная последовательность узлов, полученнаяпри прямом обходе, отражает «спуск» информацииот корня дерева к листьям.5Двоичное деревоРазличные способы обхода двоичного дерева(2)Обход в глубину в обратном порядке:обойти левое поддерево,обойти правое поддерево,обработать корень.Порядок обработки узлов дерева на рисунке:D B G E H J F C AЛинейная последовательность узлов, полученнаяпри обратном обходе, отражает «подъем»информации от листьев к корню дерева.6Двоичное деревоРазличные способы обхода двоичного дерева(3)Симметричный обход в глубину (обход всимметричном порядке):обойти левое поддерево,обработать корень.обойти правое поддерево,Порядок обработки узлов дерева на рисунке:D B A E G C H F J7Двоичное деревоРазличные способы обхода двоичного дерева(4)Обход двоичного дерева в ширину:узлы дерева обрабатываются «по уровням»(уровень составляют все узлы, находящиеся наодинаковом расстоянии от корня)Порядок обработки узлов дерева на рисунке:A B C D E F G H J8Двоичное деревоФункции, реализующие обходы двоичного дерева, позволяютпо указателю каждого узла дерева P вычислить указатели узловP_next_pre, P_next_post и P_next_in,P_pred_pre, P_pred_post и P_pred_in.Рекурсивные Си-функции обхода двоичного дерева вглубину(1)void preorder (node * r) {if (r == NULL)return;if (r->info)printf ("%c", r->info);preorder (r->left);preorder (r->right);}9Двоичное деревоРекурсивные Си-функции обхода двоичного дерева вглубину(2)void postorder (node *r) {if (r == NULL)return;postorder (r->left);postorder (r->right);if (r->info)printf ("%c", r->info);}(3)void inorder (node *r) {if (r == NULL)return;inorder (r->left);if (r->info)printf ("%c", r->info);inorder (r->right);}10Двоичное деревоНерекурсивная функция обхода двоичного дерева(управление стеком ведется не автоматически, а в самойфункции).r –указатель на корень дерева;t –указатель на корень обрабатываемого(текущего) поддерева;stack –массив,на котором моделируется стек,depth –глубина стека,top –указатель вершины стека;Стек требуется для ручного сохранения параметров функции,локальных переменных и точки возврата (если рекурсивныхвызовов функции несколько).В функции inorder нет локальных переменных, а второй из двухрекурсивных вызовов хвостовой, что позволяет не сохранятьего параметры в стекеПоэтому сохраняется только параметр функции11Двоичное деревоНерекурсивная функция обхода двоичного дереваАлгоритм:(1)[Инициализация].

Характеристики

Список файлов лекций