KMP

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n) 。

查找过程

以W="ABCDABD"，S="ABC ABCDAB ABCDABCDABDE"为例说明查找过程。查找过程同时使用两个循环变量m和i：

• m代表主文字符串S内匹配字符串W的当前查找位置，

• i代表匹配字符串W当前做比较的字符位置。

图示如下：

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456

从W与S的开头比较起。比对到S[3](=' ')时，发现W[3](='D')与之不符。接着并不是从S[1]比较下去。已经知道S[1]~S[3]不与W[0]相合。因此，略过这些字符，令 m = 4以及i = 0。

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
i:     0123456

如上所示，检核了"ABCDAB"这个字符串。然而，下一字符便不相合。可以注意到，"AB"在"ABCDAB"的头尾处均有出现。这意味着尾端的"AB"可以作为下次比较的起始点。因此，令m = 8, i = 2，继续比较。图标如下：

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:         ABCDABD
i:         0123456

于m = 10的地方，又出现不相符的情况。类似地，令m = 11, i = 0继续比较：

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
i:            0123456

这时，S[17](='C')不与W[6]相同，但是已匹配部分"ABCDAB"亦为首尾均有"AB"，采取一贯的作法，令m = 15和i = 2，继续搜索。

             1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:                ABCDABD
i:                0123456

找到完全匹配的字符串了，其起始位置于S[15]的地方。

部分匹配表

部分匹配表，又称为失配函数，作用是让算法无需多次匹配S中的任何字符。能够实现线性时间搜索的关键是在主串的一些字段中检查模式串的初始字段，可以确切地知道在当前位置之前的一个潜在匹配的位置。换句话说，在不错过任何潜在匹配的情况下，"预搜索"这个模式串本身并将其译成一个包含所有可能失配的位置对应可以绕过最多无效字符的列表。

对于W中的任何位置，都希望能够查询那个位置前（不包括那个位置）有可能的W的最长初始字段的长度，而不是重新从W[0]开始比较整个字段，这长度就是查找下一个匹配时回退的距离。因此T[i]是W的可能的适当初始字段同时也是结束于W[i - 1]的子串的最大长度。使空串长度是0。当一个失配出现在模式串的最开始，这是特殊情况（无法回退），设置T[0] = -1，在下面讨论。

创建表算法示例

以W = "ABCDABD"为例。以下将看到，部分匹配表的生成过程与前述查找过程大同小异，且出于类似原因是高效的。

首先，设定T[0] = -1。为求出T[1]，必须找到一个"A"的真后缀（真后缀指不等于原串的后缀）兼W的前缀。但"A"没有真后缀，所以设定T[1] = 0。类似地，T[2] = 0。

继续到T[3]，注意到检查所有后缀有一个捷径：假设存在符合条件的前后缀，两者分别为W[0..1] = W[1..2]，则必有W[0..0] = W[1..1]。由于W[0..0]亦是W的真前缀，上一步必然已经得到T[2] = 1（而有T[2] = 0，说明假设不成立）。一般地，遍历到每个字符时，只有上一步已经发现一个长为m的有效后缀，才需要判断有无长为m+1的后缀，而毋需考虑长为m+2、m+3等的后缀。

从而，不必考虑长为2的后缀，而唯独需要考虑的长度1亦不可行，故得到T[3]=0。

接下来是W[4] = 'A'。基于同样的理由，需要考虑的最大长度为1，并且在'A'这个情况中有效，回退到寻找的当前字符之前的字段，因此T[4] = 0。

现在考虑下一个字符W[5] = 'B'，使用这样的逻辑：如果曾发现一个子模式在上一个字符W[4]之前出现，继续到当前字符W[5]，那么在它之前它本身会拥有一个结束于W[4]合适的初始段，与事实相反的是已经找到'A'是最早出现在结束于W[4]的合适字段。因此为了找到W[5]的终止串，不需要查看W[4]。因此T[5] = 1。

最后到W[4] = 'A'。下一个字符是'B'，并且这也确实是W[5]。此外，上面的相同参数说明为了查找W[6]的字段，不需要向前查看W[4]，所以得出T[6] = 2。

于是得到下面的表：

另一个更复杂和有趣的例子：

代码实现

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 构建模式串的next数组
vector<int> getNext(string pattern) {
    int m = pattern.size();
    vector<int> next(m, 0);
    int i = 1, j = 0;
    while (i < m) {
        if (pattern[i] == pattern[j]) {
            next[i] = j + 1;
            i++;
            j++;
        } else {
            if (j > 0) {
                j = next[j - 1];
            } else {
                next[i] = 0;
                i++;
            }
        }
    }
    return next;
}
// KMP算法实现字符串匹配
int KMP(string text, string pattern) {
    int n = text.size();
    int m = pattern.size();
    vector<int> next = getNext(pattern);
    int i = 0, j = 0;
    while (i < n) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
            if (j == m) {
                return i - m;
            }
        } else {
            if (j > 0) {
                j = next[j - 1];
            } else {
                i++;
            }
        }
    }
    return -1;
}

int main() {
    string text = "ababcabaabc"; 
    string pattern = "abaabc";  // next = 0 1 1 2 3 0
    
    int result = KMP(text, pattern);
    
    if (result != -1) {
        cout << "Pattern found at index " << result << endl;
    } else {
        cout << "Pattern not found" << endl;
    }

    string t = "在计算机科学中，克努斯-莫里斯-普拉特字符串查找算法（英语：Knuth–Morris–Pratt algorithm，简称为KMP算法）可在一个字符串S内查找一个词W的出现位置。一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置，此算法利用这一特性以避免重新检查先前配对的字符这个算法由高德纳和沃恩·普拉特在1974年构思，同年詹姆斯·H·莫里斯也独立地设计出该算法，最终三人于1977年联合发表 ";
    string p = "KMP"; 
    cout << p << " index "<< KMP(t, p) << endl; // 中文字符 占用3个字节 因为UTF-8编码
        return 0;
}

优点:

1. 时间复杂度较低,在最坏情况下也只需要O(n+m)的时间复杂度,其中n是文本串长度,m是模式串长度。相比暴力匹配的O(n*m)有明显改进。

2. 对于存在多个相同字符的模式串,KMP算法可以有效避免重复比较,提高效率。

3. 算法思路简单,可读性好,容易实现。

缺点:

1. 对于某些特殊字符串,KMP算法的效率可能并不是最优的。

2. 由于需要预处理模式串,构建"部分匹配表",所以在处理大量较短模式串时,预处理过程的开销可能较大。

3. 对于模式串中某些字符较少出现的情况,KMP算法的效率可能不如Boyer-Moore算法。