Автор: Лао Цзю — Техническое Просо.
социальный контакт:CSDN
публика:Школа Лаоцзю (для новичков есть преимущества)
Специальное заявление: Нелегко быть оригинальным, и перепечатка или плагиат не допускаются без разрешения.Если вам нужно перепечатать, вы можете связаться с автором для получения разрешения.
предисловие
Объясняя алгоритм, я сначала сослался на «Мастерство алгоритмов с помощью C», опубликованное O'Reilly, веб-сайт Wiki и учебник «Структура данных (версия на языке C)» Яна Веймина. Потому что мы надеемся быть очень строгими при изучении алгоритмов с помощью различных профессиональных рекомендаций.
Введение в КМП
В книге "Mastering Algorithms with C" определения KMP я не нашел, думаю объяснение на вики стандартное, поэтому скриншот такой:
В интернете много пояснений по этому алгоритму, я не буду здесь ссылаться на перевод и не буду его повторять. Мы перечисляем это объяснение вики, а также перечисляем объяснение приложения веб-сайта для алгоритма KMP:блестящий.org/wiki/Кнут-…Вы можете обратиться и понять сами, я надеюсь, что это поможет вам понять точное определение KMP во многих отношениях.
Ниже мы представляем процесс реализации языка C.
Реализация алгоритма KMP на языке C
Идеи:
совпадение строкиЭто одна из основных задач компьютера. Возьмем «каштан»: есть строка «ааааааааакак», я хочу знать, содержит ли она еще строку «аааак»? будет использоваться здесьАлгоритмы сопоставления с образцом для строк. Существует множество алгоритмов сопоставления с образцом для строк, наиболее распространенным из которых является традиционный.Алгоритм БФиАлгоритм КМП.
Идея дизайна алгоритма BF
- Основная строка и строка шаблона сравниваются посимвольно.
2. Когда символы различаются (несоответствие), позиция сравнения основной строки сбрасывается на позицию следующего символа начальной позиции, а позиция сравнения строки шаблона сбрасывается на начальную позицию
3. Если совпадение успешно, вернуть начальную позицию совпадающей строки в основной строке, в противном случае вернуть код ошибки
Недостатки конструкции алгоритма BF
В алгоритме BF каждое несоответствие требуетотступлениеУказывает на символ рядом с начальным символом последнего сравнения! После наблюдения мы обнаружим, что при возврате кажется, что некоторые части совпадающей части не нужно сравнивать! Это уменьшает алгоритмвременная сложность.
Решения конструктивных недостатков алгоритмов BF
Алгоритм KMP (Knuth-Morris-Pratt) эффективно устраняет дефекты алгоритма BF. он назван в честь трех изобретателей, первый персонажKизвестный ученыйDonald·Knuth.
Но этот алгоритм не прост для понимания, в сети много объяснений, но читать его очень кропотливо. Далее вы подробно познакомитесь с идеей дизайна и принципом работы алгоритма KMP.
Идея дизайна алгоритма KMP
Когда символы сравниваются неравно во время сопоставления,основная строкаS сравниваемых позиций не возвращаются,строка шаблонаПозиция сравнения T перемещается.
В процессе сопоставления возникает трудная задача: как рассчитатьстрока шаблонаКоличество битов, на которое перемещается T, когда оно не совпадает?Функция частичного соответствия.
Функция частичного сопоставления — самая сложная для понимания часть алгоритма KMP. Сначала нужно понятьпрефикс,суффиксимаксимальная общая длинаКонцепция чего-либо.
префиксОтносится ко всем комбинациям заголовков строки, кроме последнего символа.
суффиксОтносится ко всем конечным комбинациям строки, кроме первого символа.
максимальная общая длина(Частичное совпадение) относится к наибольшему общему элементу в префиксе и суффиксе или 0, если нет. Например, префикс «абаб» — это «а», «аб», «аба», а суффикс — «б», «аб», «баб», поэтому максимальный общий элемент — «аб», и максимальная общая длина равна 2.
Просмотрите процесс сопоставления алгоритма KMP:
Часть, обведенная красной линией, является наибольшим общим элементом «ааа» части «аааа», совпадающей при возникновении несоответствия Эта часть символа является символом, который пропускается без повторения сравнения.
В процессе реализации кода позиция после перемещения j = начальный нижний индекс строки шаблона T + значение частичного совпадения. Обычно начальный индекс равен 0, поэтому позиция после j перемещений = значение частичного совпадения, то есть j=next[j], next[j] равноФункция частичного соответствия, j — позиция рассогласования.
Итак, следующим шагом будет реализация функции частичного сопоставления. Перечислите максимальную общую длину всех подстрок, начиная с первого символа «aaaac», образуяЧастичная таблица соответствия, который описывает взаимосвязь между индексом j при несоответствии и значением частичного совпадения.
Часть таблицы сопоставления реализована путем самосопоставления строки шаблона T:
Реализация кода языка C
Алгоритм сопоставления КМП
int KMPCompare(HString parent, HString child, int pos){
int next[255];
Get_Next(child, next);
int i = pos - 1;
int j = 0; //j用于子串child中的起始位置
while(i < parent.length && j < child.length){
if(j == 0 || parent.ch[i] == child.ch[j]){
++i;
++j;
}else{
j = next[j]; //i不变，j后退
}
}
if(j == child.length){
return (i + 1) - j;
}
return 0;
}
Реализация функции частичного сопоставления
void Get_Next(HString child, int * next){
int i = 0;
int j = -1;
next[0] = -1; //不会用到
while(i < child.length){
if(j == -1 || child.ch[i] == child.ch[j]){
++i;
++j;
next[i] = j;
}else{
j = next[j];
}
}
}
основная функция
void main(){
/*使用KMP算法匹配串*/
HString parent, child;
StrAssign_HeapString(&parent, "BBC ABCDAB ABCDABCDABDE"); //字符串赋值函数略
StrAssign_HeapString(&child, "ABCDABD");
printf("Index = %d\n", KMPCompare(parent, child, 1));
}
Наконец
Приведенная нами реализация кода определенно не самая лучшая.Это всего лишь предложение.Я надеюсь дать вам другую реализацию кода на языке C.Если будут какие-то недочёты,надеюсь вы сможете их исправить и дополнить.
Не забудьте дать большое просо❤️Подписаться + Нравится + Избранное + Комментарий + Переслать ❤️
Автор: Школа Лао Цзю — технология Big Millet.
Авторские права принадлежат автору. Для коммерческих перепечаток, пожалуйста, свяжитесь с автором для получения разрешения, а для некоммерческих перепечаток, пожалуйста, укажите источник.