https://segmentfault.com/a/1190000008575379 ## 简介 KMP 算法是一种改进的字符串匹配算法，KMP 算法是由 D.E.Knuth，J.H.Morris 和 V.R.Pratt 三人提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称 KMP 算法）。KMP 算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个 next() 函数实现，函数本身包含了模式串的局部匹配信息。 ## 暴力匹配 有一个文本串 S 和一个模式串 P，现在要查找 P 在 S 中的位置。如果用暴力匹配的思路， 并假设现在文本串 S 匹配到 i 位置，模式串 P 匹配到 j 位置，则有： 1. 如果当前字符匹配成功（即 S[i] == P[j]），则 i++，j ++，继续匹配下一个字符。 2. 如果失配（即 S[i] != P[j]），重置 i = i - (j - 1)，j = 0。相当于每次匹配失败时， i 回退，j 被置为 0。 ```cpp int violenceSearch(const std::string& str, const std::string& match) { int strLen = str.size(); int matchLen = match.size(); if (strLen < matchLen) return -1; int i = 0; int j = 0; while (i < strLen && j < matchLen) { if (str[i] == match[j]) { i++; j++; } else { i = i - j + 1; j = 0; } } return j == matchLen ? i - j : -1; } ``` ## kmp匹配 模式串`ABCABD`计算出部分匹配表，匹配表如下： | 字符 | A | B | C | A | B | D | | --- | --- | --- | --- | --- | --- | --- | | 匹配值 | 0 | 0 | 0 | 1 | 2 | 0 | ```cpp /** * 部分匹配值就是前缀和后缀的最长共有元素的长度。假设一个字符串 "hello"，它的前缀有 h、he、hel、hell， * 它的后缀有 ello、llo、lo、o。 * * 假设模式字符串为：ABCAB * * A 没有前缀和后缀，公有元素长度为 0 * AB 的前缀有 A，后缀有 B，公有元素长度为 0 * ABC 的前缀有 A、AB，后缀有 BC、C，公有元素长度为 0 * ABCA 的前缀有 A、AB、ABC，后缀有 BCA、CA、A，公有元素长度为 1 * ABCAB 的前缀有 A、AB、ABC、ABCA，后缀有 BCAB、CAB、AB、B，公有元素长度为 2 * ABCABD 的前缀有 A、AB、ABC、ABCA、ABCAB，后缀有 BCABD、CABD、ABD、BD、D，公有元素长度为 0 * 所以 ABCABD 中每个字符对于的匹配值分别为 0、0、0、1、2、0。 */ std::vector<int> getNext(const std::string &match) { int k = 0; int len = match.size(); std::vector<int> next(len, 0); for (int i = 1; i < len; ++i) { if (k > 0 && match[k] != match[i]) k = next[k - 1]; if (match[k] == match[i]) k++; next[i] = k; } return next; } int kmp(const std::string &str, const std::string &match) { std::vector<int> next = getNext(match); int k = 0; for (int i = 0; i < str.size(); ++i) { if (k > 0 && match[k] != str[i]) k = next[k]; if (match[k] == str[i]) k++; if (k == match.size()) return i - k + 1; } return -1; } ```