KMP算法简单实现（今天LNG 0:3 T1，该配合你演出的我演视而不见）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    int kmp(string S, string T) {
        // write code here
        int s = S.size(),t = T.size();
        //模式串比主串长的话
        if (S.empty() || s > t) {
            return 0;
        }

        int res = 0,next[s-1];
        //next[x]的意义是长度为x的前子串最长相同前后缀长度
        next[0] = -1;
        //第0位设置成-1 表示需要右移被匹配字符指针

        //先用双指针在模板内进行匹配
        for (int pre = -1, now = 0; now < s; ) {
            if(pre == -1 || S[pre] == S[now]){
                pre++;
                now++;
                //左右指针
                next[now] = pre;
            }else {
                pre = next[pre];
            }
        }

        //现在模式串和文本串进行匹配
        for (int patt = 0,now = 0; now < t; ) {
            if (patt == -1 || S[patt] == T[now]) {
                patt++;
                now++;
                //大小指针
                if (patt == s) {//完全匹配的情况
                    res++;
                    patt = next[patt];
                }
            }else {
                patt = next[patt];
            }
        }

        return res;

    }
};

KMP算法和朴素匹配（也称为暴力匹配）的区别

1. 匹配方式不同：

朴素匹配：从文本串的第一个字符开始，依次与模式串的每个字符进行比较，如果不匹配则移动文本串的指针，继续从下一个字符开始比较。

KMP算法：通过预处理模式串的next数组，根据已经匹配的前缀信息，确定模式串的下一个比较位置，从而避免重复匹配已经匹配过的字符。

2. 时间复杂度不同：

朴素匹配的时间复杂度为O(m*n)，其中m为模式串的长度，n为文本串的长度。

KMP算法的时间复杂度为O(m+n)，其中m为模式串的长度，n为文本串的长度。由于KMP算法避免了重复匹配，所以在大部分情况下，KMP算法的效率要高于朴素匹配。

3. 空间复杂度不同：

朴素匹配的空间复杂度为O(1)，不需要额外的空间。

KMP算法的空间复杂度为O(m)，需要额外的空间来存储模式串的next数组。

总结：KMP算法通过预处理模式串的next数组，可以在匹配过程中避免重复匹配已经匹配过的字符，从而提高匹配效率。相比之下，朴素匹配没有使用额外的空间，但效率较低。