Лекция 20. Поиск подстрок по образцу (1107995)
Текст из файла
Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.Лекция 20 Поиск подстрок по образцу20.1. Что такое поиск подстроки по образцу?20.1.1. Неформальная постановка задачи поиска по образцу.20.1.2. Формальная постановка задачи поиска по образцу.Даны текст – массив T [N] длины N и образец – массив P[m] длины m ≤ N, гдезначениями элементов массивов T и P являются символы некоторого алфавита A.Говорят, что образец P входит в текст T со сдвигом s (или, что то же самое, с позицииs + 1), если 0 ≤ s ≤ N – m и для всех i = 0, 1, …, m – 1 T[s + i] = P [i]. Сдвиг s(T, P)называется допустимым, если P входит в T со сдвигом s = s(T, P) и недопустимым впротивном случае.Задача поиска подстрок состоит в нахождении множества допустимых сдвиговs(T, P) для заданного текста T и образца P.20.1.3.
Терминология.Пусть строки x, y, w ∈ A*, ε ∈ A* - пустая строка: |x| - длина строки x; xy – конкатенациястрок x и y; |xy| = |x| + |y|; x = wy w – префикс (начало) x (обозначение w x ); x = yw w –суффикс (конец) x (обозначение w ℏ x ); если w – префикс или суффикс x, то |w| ≤ |x|;отношения и ℏ транзитивны. Для любых x, y ∈ A* и любогоa ∈ A соотношения x ℏ y и xa ℏ ya равносильны.Если S = S[r] – строка длины r, то ее префикс длины k, k ≤ r будет обозначаться Sk =S[k]; ясно, что S0 = ε, Sr = S20.2. Лемма (о двух суффиксах).Пусть x, y и z – строки, для которых x ℏ z и y ℏ z . Тогда если |x| ≤ |y|, то x ℏ y , если |x| ≥ |y|,то y ℏ x , если |x| = |y|, то x = y .Доказательство.См. рисунок.1(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.xxzxzzyyxxyxy|x| ≤ |y|y|x| ≥ |y|y|x| = |y|Рис.
1. Лемма о двух суффиксах.20.3. Простейший алгоритм.20.3.1. Проверка совмещения двух строк: посимвольное сравнение слева направо, котороепрекращается (с отрицательным результатом) при первом же расхождении. Оценкаскорости сравнения строк x и y – Θ(t + 1), где t – длина наибольшего общего префиксастрок x и y.20.3.2. Алгоритм: передвигаем P вдоль T, каждый раз увеличивая сдвиг на 1 и сравнивая P исоответствующую часть T:i = 0; while(P[i] == T[s + i]) i++; if(i == m) print("...");20.3.3.
Основной цикл:for(s = 0; s <= n – m; s++) {i = 0;while(P[i] == T[s + i]) i++;if(i == m) printf(" ");}20.3.4. Время работы в худшем случае Θ((n – m + 1)⋅m) ~ Θ(n2).2(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.Причина: информация о тексте T, полученная при проверке данного сдвига s, никак неиспользуется при проверке следующих сдвигов. Например, если для образца dddcсдвиг s = 0 допустим, то сдвиги s = 1, 2, 3, недопустимы, так как T[3] == с.20.4.
Алгоритм Кнута – Морриса – Пратта.20.4.1. Работает за время Θ(n + m).20.4.2. Префикс-функция, ассоциированная с образцом P, показывает, где в строке Pповторно встречаются различные префиксы этой строки. Если это известно, можно непроверять заведомо недопустимые сдвиги.b a c b a b a b a a b c b a bsa b a b a c aTPqb a c b a b a b a a b c b a bs'a b a b a c aTPka b a b aPqa b aPkРис. 2.
Префикс-функция:20.4.3. Пример.Пусть ищутся вхождения образца P = a b a b a c a в текст T (см. рисунок). Пустьдля некоторого сдвига s оказалось, что первые q символов образца совпадают ссимволами текста (на рисунке q = 5). Значит, символы текста от T[s+1] до T[s+q]известны, что позволяет заключить, что некоторые сдвиги заведомо недопустимы(например, на рисунке недопустим сдвиг s + 1, так как a будет напротив b, а присдвиге s + 2 – совпадение первых трех символов, и его без проверок отбросить нельзя).3(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.20.4.4. Вопрос.Пусть P[1..q] = T[s+1..s+q]; каково минимальное значение сдвига s′ > s, для которогоP[1..k] = T[s′+1..s′+k], где s′+k = s+q?Число s′ - минимальное значение сдвига, большего s, которое совместимо с тем, чтоT[s+1..s+q] = P[1..q].
Следовательно, значения сдвигов, меньшие s′ проверять ненужно. Лучше всего, когда s′ = s+q, так как в этом случае не нужно рассматриватьсдвиги s+q, s+q, …, s+q – 1. Кроме того, при проверке нового сдвига s′ можно нерассматривать первые его k символов образца: они заведомо совпадут.Чтобы найти s′, достаточно знать образец P и число q: T[s′+1..s′+k] – суффикс Pq,поэтому k – это наибольшее число, для которого Pk является суффиксом Pq. Зная k(число символов, заведомо совпадающих при проверке нового сдвига s′), можновычислить s′ по формуле s′ = s + (q – k).20.4.5.
Определение.Префикс-функцией, ассоциированной со строкой P[1..m], называется функция π: {1,2,…, m} → {0,1, …, m – 1}, определенная следующим образом:π[q] = max{k: k<q & Pk ℏ Pq }Иными словами, π[q] – длина наибольшего префикса P, являющегося суффиксом Pq.На рисунке – префикс-функция для строки P = a b a b a c a.20.4.6. Алгоритм.#inciude <stdio.h>#inciude <string.h>void KMP-Matcher(char *T, char *P) {int m, n, q, pi;n = strlen(T);m = strlen(P);pi = PrefixFunc(P);q = 0;for(i = 0; i < n; i++) {while(q > 0 && P[q + 1] != T[i]) q += pi;if(P[q + 1] == T[i]) q += 1;if(q == m) {printf("образец входит со сдвигом %d" i – m);q = pi;}int PrefixFunc(char *P) {4(с) Кафедра системного программирования ф-та ВМК МГУ, 2010Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.int m, k, pi;m = strlen(P);pi = 0; k = 0;for(q = 1; q < m; q++) {while(k > 0 && P[k + 1] != P[q]) k++;if(P[k + 1] == P[q]) k += 1;}return k;}20.4.7. Время работы.PrefixFunc выполняет ≤ (m – 1) итераций цикла for .
Стоимость каждой итерацииO(1), а стоимость всей процедуры O(m). Аналогично KMP-Matcher выполняет ≤ (n –1) итераций, и ее стоимость O(n). Следовательно, время выполнения всей процедурыO(m + n)20.4.8. Обоснование алгоритма.5(с) Кафедра системного программирования ф-та ВМК МГУ, 2010.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
