Сегодня я намерен объяснить КМП всем.
На самом деле, KMP уже давно говорит об этом, и причина, по которой я этого не написал, состоит в том, что я думаю, что не смогу написать это хорошо.Лучше упустить возможность, чем ввести детей в заблуждение. Ведь одно дело понимать себя, а другое дело уметь доходчиво объяснить.
所以为了写好这篇文章，我又去参考了很多别的资料。 В порядке. .Я обнаружил, что в Интернете слишком много статей, объясняющих КМП, но большинство из них все еще в тумане после прочтения (даже если я уже это знаю, чтение статей другой стороны все равно сбивает с толку).
Я надеюсь, что моя статья поможет:Пусть Сяобай тоже выучит КМП. Если цель будет достигнута к тому времени, пожалуйста, помогите мне с ретвитом. В противном случае нужно просто раскошелиться.
Без дальнейших церемоний, давайте начнем.
01. Графический анализ
Алгоритм KMP часто называют «алгоритмом просмотра фильмов» и предлагается по фамилии K, фамилии M и фамилии P вместе.представляет собой алгоритм сопоставления строк, улучшенный сопоставлением методом грубой силы.
Объяснения КМП я читал в интернете в основном потаблица следующего матчаНачни говорить. Но если честно, если бы я впервые увидел эту штуку, и вы мне рассказали про следующий матч-стол, я бы точно обалдел. Поэтому я собираюсь изменить манеру речи.
сказал выше,KMP — это алгоритм сопоставления строк, улучшенный путем сопоставления методом грубой силы.. Так что же такое сопоставление грубой силы? Если наша целевая строка и строка шаблона такие, как показано ниже. (Как упоминалось ранее в воскресном матче,Первым шагом во всех алгоритмах сопоставления строк является выравнивание.. Будь то брутфорс, КМП, Воскресенье, БМ одно и то же)
Насильственное сопоставление — это сравнение целевых строк и строк шаблона один за другим.
Когда A успешно совпадет, продолжаем сравнение, пока не встретим несопоставленный символ.
Затем мы корректируем строку шаблона,Начать сопоставление со следующего символа целевой строки (обратите внимание, это ядро). К сожалению, до сих пор нет совпадения (A и B)
Продолжайте с этого шага:
Пока мы не закончим весь процесс сопоставления:
Предположим, наша целевая строка имеет длину m, а строка шаблона имеет длину n. Строка шаблона сравнивается с целевой строкой не менее m раз, и, поскольку ее собственная длина равна n, теоретическая временная сложность составляет **O(m*n). ** Но мы можем видеть, что,Потому что, встретив на пути несопоставимых персонажей, можно остановиться, и не нужно сравнивать их полностью (как, например, вторая строка на рисунке выше). Таким образом, хотя теоретическая временная сложностьO(m*n), но в большинстве случаев это намного эффективнее.
Сопоставление грубой силы также известно как алгоритм BF, алгоритм шторма. Код относительно прост:
//GO
func BFSearch(haystack string, needle string) int {
l1 := len(haystack)
l2 := len(needle)
i, j := 0, 0
for i < l1 && j < l2 {
if haystack[i] == needle[j] {
i++
j++
} else {
i -= j - 1
j = 0
}
}
if j == l2 {
return i - j
}
return -1
}
Далее мы начинаем говорить о КМП. Если строка выше все еще там. В начале все так же, мы сравниваем А-А, В-В, С-С по очереди, пока не встретим первый непарный символ А-Е.
Теперь это начинает отличаться, если вы будете следовать приведенному выше матчу грубой силы. В этот момент мы должны вернуть целевую строку в позицию B, а строка шаблона должна вернуться непосредственно в голову. Но по задумке КМП,После первого совпадения, поскольку совпадение BC прошло успешно, мы знаем, что BC не равно A (обратите внимание на это логическое соотношение).:
Теперь, когда мы знаем, что BC не равно A, нам не нужно использовать A и BC для сопоставления. Затем мы напрямую используем A, чтобы пропустить BC, который не нужно сопоставлять ранее:
Продолжая адаптироваться вниз, мы обнаружили, что в округе Колумбия это невозможно.
Затем мы снова успешно сопоставили предыдущую B, тогда мы знаем, что B не равно A, поэтому мы можем напрямую пропустить предыдущую B:
То есть мы можем начать сравнение прямо с D:
Продолжайте сравнивать вниз:
К настоящему моменту вы освоили первые пятьдесят процентов КМП:В KMP, если строка шаблона и целевая строка не совпадают успешно, целевая строка не откатывается.. Теперь нам нужна новая струна, чтобы освоить следующие пятьдесят процентов:
Мы по-прежнему сопоставляем с самого начала, пока не встретимся первый несопоставленный символ:
Здесь то же самое, что и в приведенном выше примере,Поскольку наше совпадение BC было успешным, мы знаем, что BC не равно A, поэтому мы можем пропустить BC (обратите внимание на эту логику).:
Итак, мы начинаем сравнение с A:
Пока мы снова не совпадем:
Я подумал, что теперь, когда ты знаешь, как это сделать, подойди и поговори со мной. **Поскольку предыдущее совпадение B было успешным, мы знаем, что B не равно A, поэтому мы можем пропустить B. ** Конечно, следующее совпадение после пропуска напрямую не выполняется (A-D).
Вот в чем дело! ! ! Затем мы переходим к сопоставлению следующего бита. Мы обнаружили, что на этот раз наше совпадение было почти успешным, но мы застряли на последнем шаге сравнения (D-B).
Что нам теперь делать? Если мы немного изменим две строки (изменим AB внутри на XY), то, очевидно, вы знаете, с чего начать:
Но теперь вопрос в том, что AB неоднократно появляется в строке шаблона, поэтому можем ли мы сразу отказаться от AB в следующем сравнении?
Таким образом, мы выпускаем этот AB, и после его выпуска мы эквивалентны пропуску еще 2 символов в строке шаблона. (То есть следующее совпадение строки шаблона начинается с C)
На самом деле, КМП здесь практически закончен. Мы можем кратко резюмировать:
-
Если строка шаблона и целевая строка успешно совпадают, добавьте по единице как к длинной, так и к короткой строкам.
-
Если строка шаблона и целевая строка не совпадают успешно:
-
- Целевая строка не возвращается назад (Перед разделительной линией выше я говорил вам это)
- Максимальная длина строки шаблона, возвращающейся к тому же истинному префиксу и истинному суффиксу подстроки перед сопоставлением с неудачным символом** (после разделительной линии выше я сосредоточусь на этом для вас)**
Ну, я знаю, что второй случай после успешного матча выше - это немного многословно. Поэтому я взял это и сказал вам отдельно. Что означает это предложение?
Предположим, у нас есть строка abbaab:
- a, ab, abb, abba, abbaa — его истинные префиксы.
- b, ab, aab, baab, bbaab — его истинные суффиксы.
- Слово «правда»,Грубо говоря, не входит в себя.
В нашем примере выше подстрока перед неудачным символом — ABCEAB, ее самый длинный истинный префикс и истинный суффикс — AB, а максимальная длина — 2. Таким образом, мы возвращаем строку шаблона на вторую позицию.
Я предполагаю, что кто-то скажет: «Разве строка шаблона не возвращается к позиции максимальной длины истинного префикса и истинного суффикса? Тогда почему первый приведенный выше пример возвращается к исходной позиции?»
На самом деле дело не в том, что у нас нет строки шаблона поиска с возвратом, а в том, что максимальная длина на данный момент (имеется в виду максимальная длина того же истинного префикса и истинного суффикса, которые позже опускаются) фактически равна 0.
Так как же получить максимальную длину? Следующая таблица может быть представлена естественным образом.Независимо от того, понимаете ли вы следующую таблицу как нечто, описывающее максимальную длину, или следующую таблицу как нечто, используемое для возврата строки шаблона, на самом деле это нормально! ! ! Это также является причиной того, что вы видите много статей в Интернете, которые имеют непоследовательное понимание следующей таблицы.
Давайте возьмем желтый выше, чтобы объяснить, ABCEAB не содержит себя, то есть ABCEA, истинный префикс и истинный суффикс ABCEA:
- A,AB,ABC,ABCE
- A,EA,CEA,BCEA
Таким образом, максимальная длина равна 1. Для чего это 1? Мы можем просто оставить это A в следующем сравнении и начать сравнение непосредственно с B.
Обратите внимание, что если наша строка шаблона будет немного изменена следующим образом, максимальная длина F в это время будет равна 0, а не 2. Новички могут легко принять AB за самый длинный идентичный истинный префикс и истинный суффикс.
Пока что идея КМП почти закончена. Но великий бог сказал, и великий бог думает, что эту таблицу соответствий надо снова менять, иначе будут проблемы.
Почему возникает проблема, сказали мы, для KMP, **если совпадение не удается**Целевая строка не отслеживается. Если целевая строка не отслеживается, если строка шаблона всегда равна 0, означает ли это, что алгоритм не может продолжать работу? Итак, Бог изменил следующую таблицу соответствия и изменил значение следующей таблицы в позиции 0 на -1.
Так для чего это -1?Это просто кодовый трюк! Всем обратить внимание на 7 строчку кода, если нет j == -1, то если next[j] равно 0, войдет ли он в бесконечный цикл. И добавление этого предложения эквивалентно утверждению, что независимо от обстоятельств первый символ строки шаблона может быть сопоставлен (для j, в это время -1++, это все еще 0. Но в это время строка шаблона вперед Поехали. Не зависнет ли он из-за бесконечного цикла?Пожалуйста, примите во внимание, что когда нет j==-1 строки кода, бесконечный цикл застревает в процессе строки 11.)
//GO
func KmpSearch(haystack string, needle string, next []int) int {
l1 := len(haystack)
l2 := len(needle)
i, j := 0, 0
for i < l1 && j < l2 {
if j == -1 || haystack[i] == needle[j] {
i++
j++
} else {
j = next[j]
}
}
if j == l2 {
return i - j
}
return -1
}
Пока на самом деле KMP не так уж и много, да и код относительно простой. Но вот беда? Как правило, у нас нет готовой следующей таблицы для непосредственного использования. Как должна быть сгенерирована следующая таблица?
По сути, генерацию следующей таблицы тоже можно рассматривать как процесс сопоставления строк:То есть процесс сопоставления исходной строки шаблона с префиксом самой исходной строки шаблона.
Давайте поговорим об этом с помощью следующей строки: XXYXXYXXX.
Для этой строки:
- Истинные префиксы X, XX, XXY, XXYX, XXYXX.....
- Истинный суффикс - X, XX, XXX, YXXX, XYXXX.....
Чтобы облегчить понимание, я нарисовал два вида картинок (левая картинка — реальный процесс заполнения формы, а правая — процесс заполнения мозгов):
- Первый index[0] должен быть заполнен 0
- Затем заполните index[1].Если он совпадает, мы увеличиваем i и j на единицу..
- Затем заполните index[2],Если совпадения нет, вернуться j к индексу предыдущей позиции, на которую в данный момент указывает j. Здесь это 0 .
- Обратите внимание, что форма заполняется после завершения поиска с возвратом, а index[2] в это время равен 0.
- Затем мы перемещаем i и обнаруживаем, что следующий бит успешно совпадает. Добавьте единицу к i и j одновременно и заполните форму.
- Заполнив форму, мы обнаружили, что следующий бит все еще совпадает. Продолжайте двигаться i и j.
- Если совпадение по-прежнему успешно, продолжайте повторять вышеуказанные операции.
- Уведомление,Не удалось начать сопоставление здесь. Как упоминалось выше, если совпадение не удалось,Возврат j к индексу предыдущей позиции j в настоящее время указывает на. Вот это 2.
- Продолжайте этот процесс возврата. . . (Этот шаг является ядром всей следующей конструкции таблицы)
- Уведомление! Почему вы пишете здесь 2? На самом деле, это нужно для того, чтобы заполнить значение индекса позиции, где совпадение было успешно прослежено до последнего раза плюс 1.
Внимательные читатели, предполагается, что здесь есть небольшая проблема. Вынимаем заполненную форму:
Мы обнаружили, что эта таблица не совпадает с той, о которой мы говорили выше.Первая позиция следующей таблицы, которую мы упоминали выше, равна -1, а следующее значение позиции индекса для записи - это видеть истинный префикс всех подстрок впереди элемента и максимальной длины истинного суффикса. Это предложение немного неуклюже, но мы все же видим следующее.
Например, когда индекс равен 5, значение next равно максимальной длине ABCEA (истинный суффикс A, истинный префикс A, поэтому он равен 1).Но в нашей таблице ниже мы обнаруживаем, что максимальная длина записи в текущей позиции индекса. На самом деле, я хочу сказать здесь, следующая таблица, на самом деле, мы обычно называем этоЧастичная таблица соответствияили пмт.
Имеет ли эта таблица какое-либо отношение к нашей следующей таблице?Мы обнаружили, что, сдвинув эту таблицу на один бит назад, мы получили итоговую следующую таблицу.
Но но НО! ! ! Не во всех местах, где объясняется KMP, для вас упоминается концепция таблицы частичного соответствия, а в некоторых местах просто используется эта pmt в качестве следующей таблицы. **Это неправильное объяснение? Вообще-то нет! ** Поскольку я также сказал выше, следующая таблица заполняется -1 в начальной позиции, или даже первая из pmt заполняется -1 в качестве следующей таблицы, что все возможно.Потому что самое главное, как это использовать, когда вы туда доберетесь! Ведь определение следующей таблицы ей тоже дают люди!
Например, если вы не добавите -1 к первой позиции следующей таблицы, мы можем фактически удалить логику -1 в предыдущем алгоритме KMP. И добавлено отдельное суждение if для решения упомянутой выше проблемы бесконечного цикла.
02. Резюме
Последняя часть KMP подошла к концу!Серия KMP будет разделена на две части.В первой части объясняется, что делает KMP, что делает следующая таблица и что делает pmt. Вторая лекция расскажет вам о расчете следующей таблицы и оптимизации следующей таблицы.
Короче, лично я считаю, что содержание этой статьи размещено в статье, объясняющей КМП во всей сети, и качество все равно приемлемое. Если вы новичок, изучения этой статьи на самом деле достаточно.
На этом сегодняшняя тема окончена, вы ее выучили? Приходите и оставьте свои мысли в разделе комментариев!
Я собрал все решения, которые я написал, в электронную книгу с полными иллюстрациями для каждой проблемы.Нажмите, чтобы скачать