Алгоритм Кнута — Морриса — Пратта
Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — эффективный алгоритм, осуществляющий поиск подстроки в строке. Время работы алгоритма линейно зависит от объёма входных данных, то есть разработать асимптотически более эффективный алгоритм невозможно.
Алгоритм был разработан Д. Кнутом и В. Праттом и, независимо от них, Д. Моррисом[1]. Результаты своей работы они опубликовали совместно в 1977 году[2].
Содержание
Постановка задачи
Даны образец (строка) <math>\displaystyle S</math> и строка <math>\displaystyle T</math>. Требуется определить индекс, начиная с которого образец <math>\displaystyle S</math> содержится в строке <math>\displaystyle T</math>. Если <math>\displaystyle S</math> не содержится в <math>\displaystyle T</math> — вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число). При необходимости отслеживать каждое вхождение образца в текст имеет смысл завести дополнительную функцию, вызываемую при каждом обнаружении образца.
Идея
Алгоритм Ахо-Корасик также позволяет искать одну строку за линейное время. Но слабое место этого алгоритма — конечный автомат, который в явном виде строится за O(|needle|·|Σ|) операций и требует столько же памяти.
Если искать всего одну строку, каждое состояние будет иметь только один «прямой» переход. Побочные же переходы будем вычислять динамически, никак их не кэшируя.
если haystack[i] = needle[state] то state = state + 1 иначе state = побочный_переход(state, haystack[i])
Легко заметить, что суффиксные ссылки алгоритма Ахо-Корасик представляют собой префикс-функцию искомого шаблона.
Описание алгоритма и оценка времени работы
Рассмотрим сравнение строк на позиции <math>\displaystyle i</math>, где образец <math>\displaystyle S[ 0, m - 1 ]</math> сопоставляется с частью текста <math>\displaystyle \displaystyle T[ i, i + m - 1 ]</math>. Предположим, что первое несовпадение произошло между <math>\displaystyle \displaystyle T[ i + j ]</math> и <math>\displaystyle S[ j ]</math>, где <math>\displaystyle 1 < j < m</math>. Тогда <math>\displaystyle T[ i, i + j - 1 ] = S[ 0, j - 1 ] = P</math> и <math>\displaystyle a = T[ i + j ] \ne S[ j ] = b</math>.
При сдвиге вполне можно ожидать, что префикс (начальные символы) образца <math>\displaystyle S</math> сойдется с каким-нибудь суффиксом (конечные символы) текста <math>\displaystyle P</math>. Длина наиболее длинного префикса, являющегося одновременно суффиксом, есть значение префикс-функции от строки <math>\displaystyle S</math> для индекса <math>\displaystyle j</math>.
Это приводит нас к следующему алгоритму: пусть <math>\displaystyle \rm{\pi}[ j ]</math> — значение префикс-функции от строки <math>\displaystyle S[ 0, m - 1 ]</math> для индекса <math>\displaystyle j</math>. Тогда после сдвига мы можем возобновить сравнения с места <math>\displaystyle T[ i + j ]</math> и <math>\displaystyle S[ \rm{\pi}[ j ] ]</math> без потери возможного местонахождения образца. Можно показать, что таблица <math>\displaystyle \rm{\pi}</math> может быть вычислена (амортизационно) за <math>\displaystyle \Theta( m )</math> сравнений перед началом поиска. А поскольку строка <math>\displaystyle T</math> будет пройдена ровно один раз, суммарное время работы алгоритма будет равно <math>\displaystyle \Theta(m + n)</math>, где <math>n</math> — длина текста <math>\displaystyle T</math>.
Алгоритм на C#
//Префикс-функция для КМП
public static int[] PrefFunc(string x)
{
//Инициализация массива-результата длиной X
int[] res = new int[x.Length];
int i = 0;
int j = -1;
res[0] = -1;
//Вычисление префикс-функции
while (i < x.Length - 1)
{
while ((j >= 0) && (x[j] != x[i]))
j = res[j];
i++;
j++;
if (x[i] == x[j])
res[i] = res[j];
else
res[i] = j;
}
return res;//Возвращение префикс-функции
}
//Функция поиска алгоритмом КМП
public static string KMP(string x, string s)
{
string nom = ""; //Объявление строки с номерами позиций
if (x.Length > s.Length) return nom; //Поиск возвращает 0, если образец больше исходной строки
//Вызов префикс-функции
int[] d = PrefFunc(x);
int i = 0, j;
while (i < s.Length)
{
for (j = 0; (i < s.Length) && (j < x.Length); i++, j++)
while ((j >= 0) && (x[j] != s[i]))
j = d[j];
if (j == x.Length)
nom = nom + Convert.ToString(i - j) + ", ";
}
if (nom != "")
{
nom = nom.Substring(0, nom.Length - 2); //Удаление последней запятой и пробела
}
return nom; //Возвращение результата поиска
}См. также
Напишите отзыв о статье "Алгоритм Кнута — Морриса — Пратта"
Примечания
- ↑ Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.
- ↑ Donald Knuth; James H. Morris, Jr, Vaughan Pratt (1977). «[citeseer.ist.psu.edu/context/23820/0 Fast pattern matching in strings]». SIAM Journal on Computing 6 (2): 323–350. DOI:10.1137/0206024.
Ссылки
- [algolist.manual.ru/search/esearch/kmp.php Алгоритм Кнута-Морриса-Пратта] на сайте Algolist, перевод работы Thierry Lecroq, Christian Charras, [www-igm.univ-mlv.fr/~lecroq/string/node8.html Knuth-Morris-Pratt algorithm] // Цикл лекций EXACT STRING MATCHING ALGORITHMS, Université de Rouen, 1997
- [e-maxx.ru/algo/prefix_function Префикс-функция. Алгоритм Кнута-Морриса-Пратта] // E-maxx.ru, 2012
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
| ||||||||||||||||||||||||||
Отрывок, характеризующий Алгоритм Кнута — Морриса — Пратта
Провозглашение«Вы, спокойные московские жители, мастеровые и рабочие люди, которых несчастия удалили из города, и вы, рассеянные земледельцы, которых неосновательный страх еще задерживает в полях, слушайте! Тишина возвращается в сию столицу, и порядок в ней восстановляется. Ваши земляки выходят смело из своих убежищ, видя, что их уважают. Всякое насильствие, учиненное против их и их собственности, немедленно наказывается. Его величество император и король их покровительствует и между вами никого не почитает за своих неприятелей, кроме тех, кои ослушиваются его повелениям. Он хочет прекратить ваши несчастия и возвратить вас вашим дворам и вашим семействам. Соответствуйте ж его благотворительным намерениям и приходите к нам без всякой опасности. Жители! Возвращайтесь с доверием в ваши жилища: вы скоро найдете способы удовлетворить вашим нуждам! Ремесленники и трудолюбивые мастеровые! Приходите обратно к вашим рукодельям: домы, лавки, охранительные караулы вас ожидают, а за вашу работу получите должную вам плату! И вы, наконец, крестьяне, выходите из лесов, где от ужаса скрылись, возвращайтесь без страха в ваши избы, в точном уверении, что найдете защищение. Лабазы учреждены в городе, куда крестьяне могут привозить излишние свои запасы и земельные растения. Правительство приняло следующие меры, чтоб обеспечить им свободную продажу: 1) Считая от сего числа, крестьяне, земледельцы и живущие в окрестностях Москвы могут без всякой опасности привозить в город свои припасы, какого бы роду ни были, в двух назначенных лабазах, то есть на Моховую и в Охотный ряд. 2) Оные продовольствия будут покупаться у них по такой цене, на какую покупатель и продавец согласятся между собою; но если продавец не получит требуемую им справедливую цену, то волен будет повезти их обратно в свою деревню, в чем никто ему ни под каким видом препятствовать не может. 3) Каждое воскресенье и середа назначены еженедельно для больших торговых дней; почему достаточное число войск будет расставлено по вторникам и субботам на всех больших дорогах, в таком расстоянии от города, чтоб защищать те обозы. 4) Таковые ж меры будут взяты, чтоб на возвратном пути крестьянам с их повозками и лошадьми не последовало препятствия. 5) Немедленно средства употреблены будут для восстановления обыкновенных торгов. Жители города и деревень, и вы, работники и мастеровые, какой бы вы нации ни были! Вас взывают исполнять отеческие намерения его величества императора и короля и способствовать с ним к общему благополучию. Несите к его стопам почтение и доверие и не медлите соединиться с нами!»
В отношении поднятия духа войска и народа, беспрестанно делались смотры, раздавались награды. Император разъезжал верхом по улицам и утешал жителей; и, несмотря на всю озабоченность государственными делами, сам посетил учрежденные по его приказанию театры.
В отношении благотворительности, лучшей доблести венценосцев, Наполеон делал тоже все, что от него зависело. На богоугодных заведениях он велел надписать Maison de ma mere [Дом моей матери], соединяя этим актом нежное сыновнее чувство с величием добродетели монарха. Он посетил Воспитательный дом и, дав облобызать свои белые руки спасенным им сиротам, милостиво беседовал с Тутолминым. Потом, по красноречивому изложению Тьера, он велел раздать жалованье своим войскам русскими, сделанными им, фальшивыми деньгами. Relevant l'emploi de ces moyens par un acte digue de lui et de l'armee Francaise, il fit distribuer des secours aux incendies. Mais les vivres etant trop precieux pour etre donnes a des etrangers la plupart ennemis, Napoleon aima mieux leur fournir de l'argent afin qu'ils se fournissent au dehors, et il leur fit distribuer des roubles papiers. [Возвышая употребление этих мер действием, достойным его и французской армии, он приказал раздать пособия погоревшим. Но, так как съестные припасы были слишком дороги для того, чтобы давать их людям чужой земли и по большей части враждебно расположенным, Наполеон счел лучшим дать им денег, чтобы они добывали себе продовольствие на стороне; и он приказал оделять их бумажными рублями.]
В отношении дисциплины армии, беспрестанно выдавались приказы о строгих взысканиях за неисполнение долга службы и о прекращении грабежа.
Х
Но странное дело, все эти распоряжения, заботы и планы, бывшие вовсе не хуже других, издаваемых в подобных же случаях, не затрогивали сущности дела, а, как стрелки циферблата в часах, отделенного от механизма, вертелись произвольно и бесцельно, не захватывая колес.
