KMP

KMP（Knuth-Morris-Pratt）

KMP算法是一个里程碑式的算法，它的出现宣告了人类找到了最坏情况下具有线性时间复杂度的字符串匹配算法。BM算法和Sunday算法也能减少比较次数，但不能笼统地说它们都保证最坏情况下的线性时间复杂度。

KMP算法由三位计算机科学家D. E. Knuth、J. H. Morris和V. R. Pratt提出，KMP这个算法名字正是取自这三个人的姓氏首字母。

与BM算法类似，KMP算法也在试图减少无谓的字符比较，但KMP算法把专注点放在了已匹配的前缀。

在每一次匹配过程中，其实可以判断出后续几次匹配是否会成功。算法的核心就是每次匹配过程中推断出后续完全不可能匹配成功的部分，从而减少比较的次数。

例如主串中已匹配末尾的GTG是最长可匹配后缀，模式串中开头的GTG是最长可匹配前缀。

将最长可匹配后缀与最长可匹配前缀对齐。

主串中已匹配末尾的G是最长可匹配后缀，模式串中开头的G是最长可匹配前缀。

将最长可匹配后缀与最长可匹配前缀对齐。

KMP算法的整体思路就是在已匹配的前缀当中寻找最长可匹配后缀子串和最长可匹配前缀子串，在下一轮直接把两者对齐，从而实现模式串的快速移动。

那么如何找到一个字符串前缀的最长可匹配后缀子串和最长可匹配前缀子串呢？难道在每一轮都要重新遍历吗？

要找到这两个子串没有必要每次都去遍历，可以事先缓存到一个集合当中，用的时候再去集合里面取。这个集合被称为next数组，如何生成next数组是KMP算法的最大难点。

next数组

next数组实质上就是找出模式串前后字符重复出现的个数，next[i]表示模式串P[0]到P[i]这个子串使得前k个字符等于后k个字符的最大值，其中k不能取i + 1，因为子串一共才i + 1个字符，自己跟自己相等毫无意义。

例如当文本串S = "ABABAABAABAC"，P = "ABAABAC"。

已经成功匹配3个，查看next[3-1] = 1，表示最长匹配前后缀长度为1。模式串需要跳过的长度为匹配上的长度减去最长匹配前后缀长度，即3 - 1 = 2。

已经成功匹配6个，查看next[6-1] = 3，表示最长匹配前后缀长度为3。模式串需要跳过的长度为匹配上的长度减去最长匹配前后缀长度，即6 - 3 = 3。

在跳过不可能匹配的趟数后，并非再从头开始匹配，而是从之前不匹配的位置开始。

算法分析

假设模式串的长度为m，主串的长度为n。KMP算法唯一的额外空间是next数组，那么空间复杂度就是$O(m)$。

至于时间复杂度，KMP算法包括两步。第一步生成next数组，时间复杂度为$O(m)$；第二步是对主串的遍历，时间复杂度为$O(n)$。因此KMP算法的整体时间复杂度就是$O(m + n)$。

KMP

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int *get_nexts(const char *p) {
    int n = strlen(p);
    int *next = (int *)malloc(sizeof(int) * n);
    memset(next, 0, sizeof(int) * n);
    int j = 0;

    for (int i = 1; i < n; i++) {
        while (j != 0 && p[j] != p[i]) {
            j = next[j - 1];
        }
        if (p[j] == p[i]) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

int kmp(const char *s, const char *p) {
    if (p[0] == '\0') {
        return 0;
    }
    int *next = get_nexts(p);
    int j = 0;
    int s_len = strlen(s);
    int p_len = strlen(p);

    for (int i = 0; i < s_len; i++) {
        while (j > 0 && s[i] != p[j]) {
            j = next[j - 1];
        }
        if (s[i] == p[j]) {
            j++;
        }
        if (j == p_len) {
            free(next);
            return i - p_len + 1;
        }
    }

    free(next);
    return -1;
}

int main(void) {
    const char *s = "GTGTGAGCTGGTGTGTGCFAA";
    const char *p = "GTGTGCF";
    printf("%d\n", kmp(s, p));
    return 0;
}

返回第一个完整匹配的起点下标，未找到返回-1，空模式串返回0。C/C++以字节为单位，Java以UTF-16代码单元为单位，Python以字符为单位；本节示例使用ASCII字符。