KMP算法

【道德经·第二十章】 众人皆有余，而我独若遗。我愚人之心也哉！俗人昭昭，我独昏昏。俗人察察，我独闷闷。

KMP算法介绍，来自维基百科

next数组

传统的模式匹配算法中，当主串当前字符s[i]和模式串当前字符p[j]不匹配时，主串需要回溯至i=i-j+2位置，而模式串需回溯至j=1位置（下标从1开始）。引入next数组后，当主串和模式串不匹配时，只需将模式串回溯至next[j]位置，从而大大提高了匹配效率。假设我们有如下主串和模式串，关于next数组部分，跟着代码逻辑走一遍，具体过程如下：

代码实现：

void get_next(string& p, vector<int>& next) {
    int i = 1, j = 0;
    next[1] = 0; 
    while(i < p.size()) {
        if(j==0 || p[i]==p[j]){
            ++i; ++j; next[i] = j;
        } else {
            j = next[j];
        }
    }
}

int KMP(string& s, string p, vector<int>& next, int pos) {
    int i = pos, j = 1;
    while(i<=s.size() && j<=p.size()) {
        if(j==0 || s[i]==p[j]) {
            ++i; ++j;  // 继续比较后续字符
        } else {
            j = next[j];  // 模式串向右移动
        }
    }

    if(j > p.size()) 
        return i-p.size();  // 匹配成功
    else
        return 0;
}

时间复杂度分析

尽管普通模式匹配算法的时间复杂度为O(mn)，KMP算法的时间复杂度为O(m+n)，但在一般情况下，普通模式匹配的实际执行时间近似为O(m+n)，因此至今仍然被采用。KMP算法仅在主串与子串有很多“部分匹配”时才显得比普通算法快很多，其主要优点是主串不回溯。

位我上者，灿烂星空；道德律令，在我心中。