【算法】KMP算法

目录

1、暴力做法及优化

2、next数组的含义

3、匹配思路及代码

4、实现next数组

5、最终代码

kmp算法主要解决的是字符串匹配问题

1、暴力做法及优化

假设我们现在有一个长度为n的模式串p="aabaaf"，一个长度为m的模板串s="aabaabaaf"，p可能在s中有多次出现，要找出p在s中出现位置的起始下标，这里的p和s的下标都是从1开始的。

很容易想到的暴力做法就是外层遍历s，对于s中的每一个元素，都以其为起点区匹配p，当不匹配时就前往s的下一个元素，这样的时间复杂度是O(n*m)。实际上不需要回退到s的下一个位置，p也不需要重新从起始开始匹配

当从某一位开始不匹配时，因为前面的所有位置都是严格匹配的，所以是有一些额外信息在里面的，可以利用这些额外信息来减少枚举

2、next数组的含义

为了实现上面不匹配时的操作，需要定义一个next数组，next[i]表示的是p字符串中下标[1, i]这个子串的最长公共前后缀，以我们上面的p="aabaaf"为例

前缀的意思就是包含首字符，不包含尾字符的所有子串
后缀的意思就是包含尾字符，不包含首字符的所有子串
像aabaaf这个字符串
前缀有a，aa，aab，aaba，aabaa
后缀有f，af，aaf，baaf，abaaf
next[1] = 0，此时子串是a，前缀为空集，后缀也为空集
next[2] = 1，此时子串是aa，前缀为a，后缀为a
next[3] = 0，此时子串是aab，前缀为a,aa，后缀为b,ab
next[4] = 1，此时子串是aaba，前缀为a,aa,aab，后缀为a,ba,aba
next[5] = 2，此时子串是aabaa，前缀为a,aa,aab,aaba，后缀为a,aa,baa,abaa
next[6] = 0，此时子串是aabaaf，前缀为a,aa,aab,aaba,aabaa，后缀为f,af,aaf,baaf,abaaf

3、匹配思路及代码

我们通过字符串p求出next数组后，就可以利用next数组来完成字符串匹配时的操作了

解释一下为什么当遇到不匹配的位置时，可以直接让j = next[j]。当s[i]!=p[j+1]时，说明p[1, j]和
s[i - j, i - 1]这两个区间是完全匹配的，next[i]表示的是p字符串中下标[1, i]这个子串的最长公共前后缀，next[j]的值就是[1, j]这个子串的前缀和后缀最长的相等长度，在这个题目中就是2，会发现2刚好是前缀末尾的下标，所以直接用前缀来替换后缀对前面字符串的匹配

    // 匹配原数组
    for (int i = 1, j = 0; i <= m; i++)
    {
        while (j && s[i] != p[j + 1]) j = ne[j]; // 当不匹配时就一直回退，直到匹配或者j == 0
        if (s[i] == p[j + 1]) j++; // 如果回退到了匹配的位置,j++
        if (j == n) // p数组遍历完了
        {
            printf("%d ", i - n); // 打印起始位置
            j = ne[j]; // 遍历完成后回退到ne[j]的位置继续匹配
        }
    }

这里说一下为什么i从1开始，而j从0开始。i从1开始是因为s字符串是从下标1开始存储值的，j从0开始是因为最长公共前缀和可能是0，当j这个位置的最长公共前缀和是0时，j就会回退到0的位置，可以以此来特判j == 0时就不需要回退

4、实现next数组

前面我们介绍了next数组的含义,以及利用next数组去匹配的思路，现在我们介绍如何获得next数组

获得next数组实际上就是一个用p字符串自身与自身匹配的一个过程

我们使用i来表示后缀的末尾，j来表示前缀末尾

因为next[1]一定是0，一个字符既没有前缀也没有后缀，所以i是从2开始的。j从0开始

    // 构建next数组
    for (int i = 2, j = 0; i <= n; i++)
    {
        while (j && p[i] != p[j + 1]) j = ne[j]; // 当不匹配时就一直回退，直到匹配或者j == 0
        if (p[i] == p[j + 1]) j++; // 如果回退到了匹配的位置,j++
        ne[i] = j;
    }

5、最终代码

#include <iostream>

using namespace std;
const int N = 100010, M = 1000010;
char p[N], s[M];
int ne[N];
int n, m;
int main()
{
    cin >> n >> p + 1 >> m >> s + 1;
    // 构建next数组
    for (int i = 2, j = 0; i <= n; i++)
    {
        while (j && p[i] != p[j + 1]) j = ne[j]; // 当不匹配时就一直回退，直到匹配或者j == 0
        if (p[i] == p[j + 1]) j++; // 如果回退到了匹配的位置,j++
        ne[i] = j;
    }
    // 匹配原数组
    for (int i = 1, j = 0; i <= m; i++)
    {
        while (j && s[i] != p[j + 1]) j = ne[j]; // 当不匹配时就一直回退，直到匹配或者j == 0
        if (s[i] == p[j + 1]) j++; // 如果回退到了匹配的位置,j++
        if (j == n) // p数组遍历完了
        {
            printf("%d ", i - n); // 打印起始位置
            j = ne[j]; // 遍历完成后回退到ne[j]的位置继续匹配
        }
    }
    return 0;
}