题解 | #kmp算法#

题目描述
给你一个非空模板串S，一个文本串T，问S在T中出现了多少次

方法一：暴力求解

求解思路
对于本题目要求出模板串S在文本串T中出现的次数，我们想到直接从文本串T的第一个位置往后寻找模板串S长度的子串，然后拿出来和S比较即可，并且我们设置res变量来记录相同的个数。

解题代码

class Solution {
public:
    int kmp(string S, string T)
    {
        if(S.empty() || S.size() > T.size()) return 0; // 边界
        int hyres = 0, next[S.size() + 1];
        next[0] = -1;
        for(int pre = -1, cur = 0; cur < S.size();)
        {
            if(pre == -1 || S[pre] == S[cur])
            {   //暴力匹配
                pre++;
                cur++;
                next[cur] = pre;
            }
            else pre = next[pre];
        }
        for(int pattern = 0, cur = 0; cur < T.size();)
        {   //模板串匹配
            if(pattern == -1 || S[pattern] == T[cur])
            {
                pattern++;
                cur++;
                if(pattern == S.size())
                {   //如果完全匹配
                    hyres++; // 结果加1
                    pattern = next[pattern];
                }
            }
            else pattern = next[pattern];
        }
        return hyres; // 返回结果
    }
};

复杂度分析
时间复杂度：一层循环加上一遍字符串遍历，因此时间复杂度为，N为循环，M为字符串子串的长度。
空间复杂度：没有引入额外的内存地址空间，因此空间复杂度为

方法二：KMP优化求解

求解思路
对于字符串子串匹配算法，我们使用KMP进行求解，首先构建一个next数组，用next[i]来表示模板串S中最长公共前缀的结束的下标，并且next[0]赋值-1。接着进行匹配，若匹配成功则两个字符串同步前进，若匹配失败则继续往前搜索到next数组中的位置，若为完全匹配，则跳到当前子串起始位置后一个，并更新到next的最后一个匹配值，来重新匹配下一个字符串。

解题代码

class Solution {
public:
    int kmp(string S, string T) {
        int n = T.length(); // 保存T的长度
        int m = S.length(); // 保存S的长度
        int hyres = 0;
        vector<int> next(m + 1); // 声明next数组
        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最大值
                    hyres++; // 结果加1
                    k = next[k];
                }
            }
            else //否则继续往前搜索
                k = next[k];
        }
        return hyres; // 返回结果
    }
};

复杂度分析
时间复杂度：一层循环，因此时间复杂度为
空间复杂度：因为引入next数组，所以空间复杂度为,N为next数组的长度。