KMP算法

KMP英文全称为Knuth-Morris-Pratt

暴力算法在遇到字符不匹配时，会将模式串直接向右移动一位，然后从头比较，时间复杂度最高可达 $O(m \times n)$。

KMP 算法的核心思想是：当发生不匹配时，可根据模式串的LPS数组，将模式串向右移动到下一个仍然可能匹配的位置，避免了无谓的重复比较。

LPS 数组

LPS 数组（Longest Proper Prefix which is also Suffix，最长公共前后缀长度）。 记录了模式串中每个子串的“最长相等前后缀”的长度。

• 前缀（Prefix）： 包含首字母，但不包含尾字母的所有子串。
• 后缀（Suffix）： 包含尾字母，但不包含首字母的所有子串。

以模式串 ABABACA 为例，我们计算它每个位置的 LPS 值：

LPS 数组本身记录的就是前缀的内部对称性。当第 $i$ 个字符匹配失败时，由于前面的字符已经匹配成功，我们可以利用已知信息，直接跳到上一个最长公共前后缀的末尾继续比较，从而避免无谓的从头回溯。

构建LPS 数组

初始状态为：

i = 1;
len = 0;
lps[0] = 0;

含义：

• i：当前需要计算 lps[i] 的位置；
• len：当前已经找到的最长相等前后缀长度。

共有三种情况

1. 字符相等

    len++;
    lps[i] = len;
    i++;

2. 字符不相等的同时 len > 0

    len = lps[len - 1];

   • 这种情况意味着公共前后缀扩展失败，我们需要寻找次长的公共前后缀。len = lps[len - 1]，这部分前后缀相同，可以保证退回后的那几个字符与i所在的那几个字符绝对相同，可以继续往下比较。

3. 字符不相等的同时 len = 0

   lps[i] = 0;
   i++;

   • 万策尽，无法继续缩短，只能遗憾等于0了。

具体代码

void computeLPSArray(char *pat, int n, int *lps) {
    int i = 1;      
    int len = 0;    //记录当前最长公共前后缀的长度
    lps[0] = 0;     //一个字符的lps只能为0

    while (i < n) {
        if (pat[len] == pat[i]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len > 0) {
                //寻找次长的公共前后缀
                len = lps[len - 1];
            } else {
                // 回退到了 0 仍然不匹配
                lps[i] = 0;
                i++;
            }
        }
    }
}

KMP匹配过程

主串指针永远不回退，只调整模式串指针。

具体可看代码实现

具体代码

void KMPSearch(char* pat, char* txt) {
    int i = 0;              //指向txt
    int j = 0;              //指向pat
    int m = strlen(txt);
    int n = strlen(pat);

    int *lps = new int[n];      //动态创建lps数组的长度
    computeLPSArray(pat, n, lps);   

    while (i < m) {
        if (txt[i] == pat[j]) {      
            i++;
            j++;
        }

        if (j == n) { 
            //意味着已经对比已经走完模式串，打印结果，并退回到次长公共前后缀继续搜索
            std::cout << "起始索引为:" << i - j << std::endl;
            j = lps[j - 1];
        }

        else if (i < m && txt[i] != pat[j]) {
            //注意i不要超过主串的长度
            if (j != 0) {
                //模式串退回次长公共前后缀继续搜索
                j = lps[j - 1];
            } else {
                //万策尽，退无可退，当前字符串已经没救了，主串移动
                i++;
            }
        }
    }
    delete[] lps;       //记得释放内存
}

算法复杂度分析

• 时间复杂度：$O(m + n)$。 构建 lps 数组只需要遍历一次模式串（长度 $n$）。搜索阶段中 i 不回退，j 的前进和回退总次数都是线性的，因此为 O(m)。
• 空间复杂度：$O(n)$。 因为需要开辟一个大小为 $n$ 的 lps 数组来存储模式串的特征。

完整代码

#include <iostream>
#include <string.h>

void computeLPSArray(char *pat, int n, int *lps) {
    int i = 1;      
    int len = 0;    //记录当前最长公共前后缀的长度
    lps[0] = 0;     //一个字符的lps只能为0

    while (i < n) {
        if (pat[len] == pat[i]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len > 0) {
                //寻找次长的公共前后缀
                len = lps[len - 1];
            } else {
                // 回退到了 0 仍然不匹配
                lps[i] = 0;
                i++;
            }
        }
    }
}

void KMPSearch(char* pat, char* txt) {
    int i = 0;              //指向pat
    int j = 0;              //指向txt
    int m = strlen(txt);
    int n = strlen(pat);

    int *lps = new int[n];      //动态创建lps数组的长度
    computeLPSArray(pat, n, lps);   

    while (i < m) {
        if (txt[i] == pat[j]) {      
            i++;
            j++;
        }

        if (j == n) { 
            //意味着已经对比已经走完模式串，打印结果，并退回到次长公共前后缀继续搜索
            std::cout << "起始索引为:" << i - j << std::endl;
            j = lps[j - 1];
        }

        else if (i < m && txt[i] != pat[j]) {
            //注意i不要超过主串的长度
            if (j != 0) {
                //模式串退回次长公共前后缀继续搜索
                j = lps[j - 1];
            } else {
                //万策尽，退无可退，当前字符串已经没救了，主串移动
                i++;
            }
        }
    }
    delete[] lps;       //记得释放内存
}

int main() {
    char txt[] = "ABABDABACDABABCABAB";
    char pat[] = "AB";
    
    std::cout << "目标字符串:" << txt << std::endl;
    std::cout << "搜索模式串:" << pat << std::endl;
    
    KMPSearch(pat, txt);
    
    return 0;
}