字符串匹配算法

字符串匹配-KMP

参考文章: https://blog.csdn.net/yyzsir/article/details/89462339 https://leetcode.cn/leetbook/read/array-and-string/cpoo6/

点击查看【bilibili】
相较于普通的回溯比较, KMP算法采用每当从某个起始位置开始一趟比较后，在匹配过程中出现失配，不回溯i，而是利用已经得到的部分匹配结果，将一种假想的位置定位“指针”在模式上向右滑动尽可能远的一段距离到某个位置后，继续按规则进行下一次的比较。

next数组

一个用于记录最长公共前后缀长度的数组, 且最长公共前后缀要小于已匹配子串长度

将模式串的公共前缀移动到原来公共后缀位置

求next数组

造方法为：next[i] 对应的下标，为 P[0…i - 1] 的最长公共前缀后缀的长度，令 P[0] = -1。 具体解释如下：

例如对于字符串 abcba：

前缀：它的前缀包括：a, ab, abc, abcb，不包括本身；
后缀：它的后缀包括：bcba, cba, ba, a，不包括本身；
最长公共前缀后缀：abcba 的前缀和后缀中只有 a 是公共部分，字符串 a 的长度为 1。
所以，我们将 P[0…i - 1] 的最长公共前后缀的长度作为 next[i] 的下标，就得到了 next 数组。

int* buildNext(char* P) { // 构造模式串 P 的 next 表
    size_t m = strlen(P), j = 0; // “主”串指针
    int* N = new int[m]; // next 表
    int  t = N[0] = -1; // 模式串指针
    while (j < m - 1)
        if ( 0 > t || P[j] == P[t]){ // 匹配
            j++; t++;
            N[j] = t;
        }
        else t = N[t];  // 失配
    return N;
}

int match (char* P, char* S){ // KMP 算法
    int* next = buildNext(P); // 构造 next 表
    int m = (int) strlen (S), i = 0; // 文本串指针
    int n = (int) strlen(P), j = 0; //模式串指针
    while (j < n && i < m) // 自左向右逐个比对字符
        if (0 > j || S[i] == P[j]) // 若匹配，或 P 已移除最左侧
            {i++; j++;} // 则转到下一字符
        else
            j = next[j]; // 模式串右移（注意：文本串不用回退）
    delete [] next; // 释放 next 表
    return i - j;
}