描述
给你一个文本串 T ，一个非空模板串 S ，问 S 在 T 中出现了多少次
数据范围：，
要求：空间复杂度，时间复杂度

这是典型的字符串模式匹配问题，方法一首先使用暴力算法，即S中的字符与T中的字符一个一个进行比较，当T中以第i个字符开始的字符串无法与S进行完全配对时，就继续从i+1个字符开始配对，而此时S从开始位置进行匹配。这种方法易于理解，但是时间复杂度很高，因此代码因超时不通过。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    int BFMatching(string s1, string s2, int pos)
    {
        int len1 = s1.length();
        int len2 = s2.length();
        if(len2 > len1 || !len2) return -1;
        int i = pos, j = 0;
        while(i<len1 && j<len2){
            if(s1[i] == s2[j]){
                j++;i++;//当前字符匹配成功，各自向后
            }
            else{
                i = i-j+1;j = 0;//如果失败模式串从开始位置出发，主串移动下一位置
            }
        }
        if(j==len2) return i-j+1;
        return -1;
    }
    int kmp(string S, string T) {
        // write code here
        int ss=S.size();//模板串
        int tt=T.size();//文本串
        int count=0;
        int k=0;
        while(k<tt-ss)
        {
            int index=BFMatching(T, S, k);//返回匹配到的开始位置
            if(index!=-1)
            {
                count++;
                k=index;
            }
                
        }
        return count;
        
    }
};

复杂度分析

• 时间复杂度：暴力匹配算法将两个字符串的字符一一比较，时间复杂度为$O(len(S)len(T))$，len(T)，len(S)分别表示主串与模式串的长度
• 空间复杂度：该算法的空间复杂度为$O(len(S))$

    分析方法一中的算法，可以给我们一些有用的信息。方法一中，暴力解法在每一次配对失败后，都会从T中的下一个字符开始与S中的字符开始匹配，每次匹配失败后并没有对下一次的匹配产生帮助。因此引入KMP算法，KMP算法是一种改进的字符串匹配算法，KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。要移动的位数我们把它定义成一个数组，这个数组就称之为next数组，而next数组的值是代表着字符串的前缀与后缀相同的最大长度(不能包括自身)。“前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。
具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。举例如下：

      要想查找最大前后缀，在每次匹配之后都要重新“从头”开始查找，然而，当我们前面已经匹配成功k个字符时，第$k+1$个字符匹配失败了，那么我们需要将模式串从头开始重新匹配，但是如果我们细心点我们可以发现，前面$k$个字符同样包含最大前后缀，因此令$j=next[j-1]$实质上就是将模式串回溯到前面$k$个字符所拥有的最大前后缀的位置上也就是说在求解next[j]时，必然包含前面最大前后缀长度的，因此先回溯到前面的最大前后缀的位置上，然后比较新增加的字符。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    vector<int> Next;
    void next_function(string S)
    {
        Next.push_back(-1);
        int j=0;
        for(int i=1;i<S.size();i++)
        {
            while(j>0&&S[j]!=S[i])//前缀与后缀
            {
                j=Next[j-1];
            }
            if(S[j]==S[i])
                j++;
            Next.push_back(j);
        }
    }
    int kmp(string S, string T) {
        // write code here
        int ss=S.size();//模板串
        int tt=T.size();//文本串
        int count=0;
        int j=0;
        next_function(S);//计算next数组
        for(int i=0;i<tt;i++)
        {
            while(j>0&&S[j]!=T[i])
            {
                j=Next[j-1];//如果测试的两个字符不相等，i不动，j变为当前测试字符串的next值
            }
            if(S[j]==T[i])
                j++;////S[i]==T[j],对应位置字符相等指向当前测试的两个字符串下标i和j都向后移
            if(j==ss)
            {
                count++;
                j=Next[j-1];//继续向后移动寻找，j变为当前测试字符串的next值
            }
        }
        return count;
    }
};

复杂度分析

• 时间复杂度：需要预先处理得到next数组，时间为$O(len(S))$，然后遍历一次主串，时间复杂度为$O(len(T))$，总的时间复杂度为$O(len(S)+len(T))$
• 空间复杂度：需要设置一个next数组，空间复杂度为$O(len(S))$