从正文串S中查找目标串T，T也称为模式串。可以只查找一次，找到后立即返回第一次出现的位置，也可以查找全部出现的位置。

规定字符串匹配成功时返回第一个字符的下标，且下标从0开始，如果匹配失败则返回-1。

参考链接：

本篇只记录个人对KMP算法的总结，如果想从零基础开始学习KMP算法，建议看以上两篇讲解，或者参考其他写得更为详细的讲解。

BF算法

Brute Force，暴力算法，枚举S所有的子串，看与T串是否匹配，可以很容易地写出下面的代码：

int BF(string s, string t, int pos) {
    int i, j;
    int slen = s.length();
    int tlen = t.length();
    for(i = pos; i < slen - tlen + 1; i++) {
        for(int j = 0; j < tlen; j++) {
            if(s[i+j] != t[j]) {
                break;
            }
        }
        if(j == tlen) { // 匹配成功
            return i;
        }
    }
    return -1;
}

上面的匹配过程重点是i从s串从前往后移动，而j则是每次从t串的起始位置开始匹配，可以调整一下代码，将bf算法的代码写成下面这样的形式，以更加直观地看到代码中对于i和j的回退操作：

int BF2(string s, string t, int pos) {
    int i = pos;
    int j = 0;
    int slen = s.length();
    int tlen = t.length();
    while(i < slen && j < tlen) {
        if(s[i] == t[j]) {
            i++, j++;
        } else {
            i = i - j + 1;  // i回退到上一轮开始比较的下一个字符
            j = 0;          // j回退到第一个字符
        }
    }
    if(j == tlen) {
        return i - tlen;
    } else {
        return -1;
    }
}

暴力匹配算法示意图如下：

KMP算法

针对暴力算法进行改进，改进的思路是如果S串和T串在位置j发生不匹配，则j之前的S串和T串是全部匹配的，可以通过一定的方法省去一些匹配步骤，不需要让j再从头开始匹配。

KMP算法的具体操作：计算出T串在位置j处的最大公共前后缀，如果在j处发生不匹配，则将j之前的最大公共前缀直接挪到最大公共后缀的位置，从而省去对最大公共前缀的比较，如下：

上面的操作其实等价于在j位置发生不匹配时，i保持不动，j回退到最大公共前缀的后一位继续比较。由于i不回退，所以KMP算法在比较S串和T串时的时间复杂度为O(n)级别，其中n为S串的长度。

由于在任何位置都有可能发生不匹配，所以需要计算出T串在每个位置的最大公共前后缀长度，这也是KMP算法的重点，记T串在位置j处的最大公共前后缀长度为next[j]，则next[j]的值可以分为以下两种情况：

  1. j等于0，此时j指向T串的首字符，j之前不存在字符串，也就不存在最大公共前后缀，这里可以将next[j]设置为-1，以表示next[j]不存在。（实际上设置成其他负值也可以，但设置成-1可以方便计算，以便统一代码形式，这点请参考get_next()函数进行理解。）
  2. j不等于0，此时j前面存在字符串，也就存在最大公共前后缀，next[j]表示j前面的字符串的最大公共前后缀长度，注意，next[j]可以为0，表示j前面的字符串最大公共前后缀长度为0。典型地，当j等于1时，j前面的字符串长度为1，由于前后缀不能包含字符串本身，所以next[1]的值必然为0。

关于next[j]的计算代码如下：

int slen, tlen, next[10000+5];

void get_next(string t) {
    next[0] = -1;
    int j = 0, k = -1;
    while(j < tlen) {
        if(k == -1 || t[j] == t[k]) {
            next[++j] = ++k;
        } else {
            k = next[k];
        }
    }
}

假设next[j]=k，则以上代码对应的示意图如下：

这里重点需要理解的是在t[j]与t[k]不相等时，k回退到next[k]的操作，也就是k=next[k]。

计算出next数组后，整个KMP算法的实现如下：

int KMP(string s, string t, int pos) {
    int i = pos;
    int j = 0;
    slen = s.length();
    tlen = t.length();
    
    get_next(t);

    while(i < slen && j < tlen) {
        if(j == -1 || s[i] == t[j]) {
            i++, j++;
        } else {
            j = next[j];
        }
    }
    if( j == tlen) {
        return i - tlen;
    } else {
        return -1;
    }
}

到此已经可以解决28. 实现 strStr() - 力扣（LeetCode）这个问题。

KMP算法优化

当t[k]=t[j]时，原则上next[j+1]=k+1，但当t[j+1]=t[k+1]时，回退到k+1没有意义，因为s[i+1]与t[j+1]是不相等的，那么s[i+1]与t[k+1]也必然不相等，所以这次回退可以直接判定不匹配，这时，应该让next[j+1]再回退一次，回到next[k+1]，从而减少一次不必要的比较。

只需要改进next数组的计算方法，KMP算法的主体不需要调整，改进后的算法如下，为了区别前面的版本，这里将函数命名为get_nextval()，将计算结果存到nextval数组中：

int slen, tlen, nextval[10000+5];

void get_nextval(string t) {
    nextval[0] = -1;
    int j = 0, k = -1;
    while(j < tlen) {
        if(k == -1 || t[j] == t[k]) {
            j++, k++;
            if(j < tlen && t[j] == t[k]) {
                nextval[j] = nextval[k];
            } else {
                nextval[j] = k;
            }
        } else {
            k = nextval[k];
        }
    }
}

这里不需要考虑要不要多次回退的问题，因为get_nextval()是从前往后处理的，如果回退位置上有多个相同的字符，则get_nextval()在处理时，会先让第一个字符回退到底，然后后面的字符依次继承前面的回退位置，也就是后面的相同字符全部都是一次回退到底，不需要多次回退，这里贴一个get_next()和get_nextval()计算结果的对比，对比一下结果就知道了：

这里通过get_nextval计算出来的e的回退位置全部是0，效果就是不管在哪个位置不匹配，都可以一次回退到底，不需要多次回退。

KMP算法复杂度

假设S串和T串的长度分别为n，m，则KMP算法的算法复杂度为O(n+m)，因为S串和T串都只需要扫描一遍。



















  • 无标签