(Owed by: 春夜喜雨 http://blog.csdn.net/chunyexiyu)

参考：参考使用gpt3.5查询了kmp信息资料

引言：

KMP字符串匹配算法是早有耳闻的，但之前并未去了解它的字符串匹配思路；

昨天晚上偶然翻书看到，发现算法设计思路非常棒，在自己看来，可以用惊艳来形容。

之前想来，字符串匹配，无外乎字符串从前往后遍历，然后使用查找匹配串进行匹配，匹配到一个字符，就继续往后匹配，匹配失败了，回退匹配点，继续向后匹配。

觉得KMP也差不多，想来只当是寻常，但实际上KMP匹配过程要巧妙的多。

1. 关于KMP算法：

KMP 算法是一种用于字符串匹配的经典算法，它的全称是 Knuth-Morris-Pratt 算法。

KMP核心思想

KMP算法的核心思想是，在匹配过程中，重用匹配串已经匹配过的信息，避免了在文本中重复进行不必要的比较。

KMP算法

KMP 算法通过预处理模式串（要匹配的字符串），构建一个部分匹配表（也称为 next 数组），然后利用这个部分匹配表在主串（文本串）中进行匹配。这样可以减少匹配过程中的回溯，减少比较次数，提高匹配效率。

首先：构建部分匹配表（next 数组），对于模式串 pattern，计算出以每个位置为结束的子串的最长前缀和最长后缀相等的长度，存储在 next 数组中。

然后：遍历字符串，使用模式串进行匹配；每当匹配到一定长度到某个字符匹配失败时，则参考部分匹配(next数组）快速移动模式串，进行重匹配，使用最大可能匹配长度继续匹配。

KMP算法优势：

KMP 算法具有较高的匹配效率，时间复杂度为 O(m+n)，其中 m 为模式串的长度，n 为主串的长度。

通过预处理模式串构建部分匹配表，可以减少不必要的比较，提高匹配效率。

2. KMP算法匹配例子：

假设要在字符串 text 中查找模式串 pattern：“ababac”，首先构建部分匹配表，构建出的匹配表形如：pattern table[0 0 1 2 3 0 ]

注：match过程，i为text游标，j为pattern游标

然后根据表中的信息在主串中进行匹配，假如字符串text为：”ababadabababac“

注：match过程，i为text游标，j为pattern游标

pattern table[0 0 1 2 3 0 ]

i=0, j=0, compare text[0]-{a} with pattern[0]-{a}

i=1, j=1, compare text[1]-{b} with pattern[1]-{b}

i=2, j=2, compare text[2]-{a} with pattern[2]-{a}

i=3, j=3, compare text[3]-{b} with pattern[3]-{b}

i=4, j=4, compare text[4]-{a} with pattern[4]-{a}

i=5, j=5, compare text[5]-{d} with pattern[5]-{c}

–compare not equal switch j to table[j-1]=3

i=5, j=3, compare text[5]-{d} with pattern[3]-{b}

–compare not equal switch j to table[j-1]=1

i=5, j=1, compare text[5]-{d} with pattern[1]-{b}

–compare not equal switch j to table[j-1]=0

i=5, j=0, compare text[5]-{d} with pattern[0]-{a}

i=6, j=0, compare text[6]-{a} with pattern[0]-{a}

i=7, j=1, compare text[7]-{b} with pattern[1]-{b}

i=8, j=2, compare text[8]-{a} with pattern[2]-{a}

i=9, j=3, compare text[9]-{b} with pattern[3]-{b}

i=10, j=4, compare text[10]-{a} with pattern[4]-{a}

i=11, j=5, compare text[11]-{b} with pattern[5]-{c}

–compare not equal switch j to table[j-1]=3

i=11, j=3, compare text[11]-{b} with pattern[3]-{b}

i=12, j=4, compare text[12]-{a} with pattern[4]-{a}

i=13, j=5, compare text[13]-{c} with pattern[5]-{c}

match index: 8

3. KMP样例代码：

参考gpt3.5生成的代码

kmp-pattern-table生成算法，kmp匹配算法

#include 
#include 
std::vector compute_kmp_table(const std::string& pattern) {
    int len = pattern.length();
    std::vector table(len, 0);
    int i = 1, j = 0;
    while (i < len) {
        if (pattern[i] == pattern[j]) {
            j++;
            table[i] = j;
            i++;
        } else {
            if (j != 0) {
                j = table[j - 1];
            } else {
                table[i] = 0;
                i++;
            }
        }
    }
    return table;
}
int kmp_search(const std::string& text, const std::string& pattern) {
    std::vector table = compute_kmp_table(pattern);
    int m = text.length();
    int n = pattern.length();
    int i = 0, j = 0;
    while (i < m) {
        printf("i=%d, j=%d, compare text[%d]-{%c} with pattern[%d]-{%c}\n", i, j, i, text[i], j, pattern[j]);
        if (text[i] == pattern[j]) {
            i++;
            j++;
            if (j == n) {
                return i - j; // match succ
            }
        } else {
            if (j != 0) {
                printf("--compare not equal switch j to table[j-1]=%d\n", table[j - 1]);
                j = table[j - 1];
            } else {
                i++;
            }
        }
    }
    return -1; // match failed
}

(Owed by: 春夜喜雨 http://blog.csdn.net/chunyexiyu)