题解 | #kmp算法#

思路：

题目的主要信息：

在文本串T中找到模板串S出现的次数
S不为空
要求时间空间最多为 $O(n)$

方法一：暴力法（不会超时，但不符合要求）
具体做法：
遍历文本串，每次截取下标后m个与文本串比较，如果相同则答案加一。需要注意后面要留出m位防止访问越界。

class Solution {
public:
    int kmp(string S, string T) {
        int n = T.length();
        int m = S.length();
        int res = 0;
        for(int i = 0; i <= n - m; i++){ //遍历文本串
            if(T.substr(i, m) == S)  //找到字串
                res++;
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(nm)$ ，遍历为 $O(n)$ ，比较每次为 $O(m)$
空间复杂度： $O(1)$ ，无额外空间使用

方法二：KMP思想
字符串的字串匹配算法要优化，我们可以想到KMP算法。
具体做法：
像KMP算法一样，构建一个next数组，next[i]表示模式串S中最长公共前缀后缀的前缀结束的下标，从-1开始。
图片说明
匹配的时候，若是匹配成功，则两个字符串同步前进，若是匹配失败则继续往前搜索到next数组中的位置，若是完全匹配，跳到当前字串起始位置后一个，更新到next的最后一个匹配值，重新匹配下一个字串。

class Solution {
public:
    int kmp(string S, string T) {
        int n = T.length();
        int m = S.length();
        int res = 0;
        vector<int> next(m + 1); 
        next[0] = -1;  //next数组从-1开始
        int k = -1;
        for(int i = 0; i < m;){  //初始化next数组
            if(k == -1 || S[k] == S[i]){
                k++;
                i++;
                next[i] = k;
            }
            else
                k = next[k];
        }
        k = 0;  //每次next数组从0开始，后面访问都会+1
        for(int i = 0; i < n;){
            if(k == -1 || T[i] == S[k]) {//若是匹配，k 与 i 一同加
                k++;
                i++;
                if(k == m){ //找到一个，将k置为next最大值
                    res++;
                    k = next[k];
                }
            }
            else  //否则继续往前搜索
                k = next[k];
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，不管初始化next数组，还是匹配字串都是一次遍历
空间复杂度： $O(m)$ ，next数组的空间， $m<n$