KMP算法

目录
– KMP算法
– 研究背景
– 前置概念
– 实现原理
– 代码实现

研究背景

KMP算法是解决字符串匹配问题的一种算法, 其效果就是在一个字符串中找到另一个字符串的位置(类似于indexOf()方法)

$M$为原字符串长度, $N$ 为目标字符串长度
暴力解法的时间复杂度为 $O(M*N)$
KMP算法的时间复杂度为 $O(M+N)$.

前置概念

“字符串前缀和后缀相同的最大长度” 是核心概念
+ 前缀就是字符串头部的子串
+ 后缀就是字符串尾部的子串

注意, 前后缀都不能是整个字符串, 也不能是空字符串

举个例子: abcab
+ 前缀有: a, ab, abc, abca
+ 后缀有: b, ab, cab, bcab

我们希望能找到一个最大长度, 使得该长度的前缀和后缀相同
那么对于abcab而言, 最大长度的相同前后缀就是ab, 那么这个最大长度也就是2

实现原理

假设我们事先得到了所有位置的前面的一整个字符串的最大前后缀相同长度的next数组

“前面”的意思是不包括本字符串, 比如2位置上对应的前面的字符串就是ab, 而不是abc

并且我们还人为规定, 第0位是-1, 第1位是0

比如: abcab的next数组为: -1 0 0 0 2
再比如: abacabad的next数组为: -1 0 0 1 0 1 2 3

KMP算法的核心思想就是利用next数组中的信息, 来减少无用的比较(已经比较过的不再比较)

如下图:

当我们在第二个X位置匹配失败之后, 通过读取Z位置上的next数组, 我们可以知道”比较字符串”前方有前后缀相同的字符串
那么下一次比较让”比较字符串”的头部和后缀的开头对齐即可, 并且可以直接从匹配出错的位置(对于原字符串而言)开始匹配

当然, 如果出现了next数组的值为0的情况, 或是第一位就匹配出错的情况, 那么比较字符串只要后移一位即可

那么如何得到next数组呢?
可以用到动态规划的思路
首先0 1两位上确定, 后续每一位都依赖于前一位推出
只要比较前一位前缀位置后的那个和前一个位置上的字符是否相等即可
+ 如果一样, 那么该位置的next值就是前一位的next值加一
+ 如果不一样, 那么前缀位置后的那个向前跳, 直到跳到-1或者是相等, 那么该位置的next值就是跳到的位置的next值加一

代码实现

vector<int> getNextArrary(string str)
{
    vector<char> s = vector<char>(str.begin(), str.end());
    int len = s.size();
    vector<int> next(len, 0);
    next[0] = -1;
    next[1] = 0;
    int p = 2;      // next数组的指针(当前还未确定的位置)
    int k1 = -1;    // p-1位置前缀的最后的位置
    int k2 = 0;     // p-1位置前缀的长度
    while (p < len - 1)
    {
        while(k1 != -1 && s[p - 1] != s[k1+1])
        {
            k2 = next[k1+1];
            k1 = k2-1;
        }
        if(k1 != -1){
            next[p] = k2 + 1;
            k1 = k2++;
        }
        else{
            if(s[p-1] == s[0]){
                next[p] = 1;
                k1 = 0;
                k2 = 1;
            }
            else{
                next[p] = 0;
            }
        }
        p++;

    }
    return next;
}

int KMP(string originStr, string cmpStr)
{
    if (originStr == "" || cmpStr == "" || originStr.size() < cmpStr.size())
        return -1;
    vector<char> origin = vector<char>(originStr.begin(), originStr.end());
    vector<char> cmp = vector<char>(cmpStr.begin(), cmpStr.end());
    vector<int> next = getNextArrary(cmpStr);
    int i1 = 0;
    int i2 = 0;
    while (i1 < origin.size() && i2 < cmp.size())
    {
        if (origin[i1] == cmp[i2])
        {
            i1++;
            i2++;
        }
        else if (i2 == 0)
        {
            // 该情况是匹配字符串第一位还是不匹配, 那只好将源字符串往后移动一位, 换一个开头再试
            // 条件也能等价为next[i2] == -1
            i1++;
        }
        else
        {
            // 能跳
            i2 = next[i2];
        }
    }
    return i2 == cmp.size() ? i1 - i2 : -1;
}