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

方法：
kmp

思路：
        kmp算法本质要求模式串的 next[ ]数组，next[ i ]表示模式串0 ~ i 的最长公共前后缀的长度。
        kmp算法对文本串不会回溯，只是通过next[ ]回溯模式串。
        
        核心思想：next[ ] 数组存储的最长公共前后缀长度，与在模式串中即将转跳的 下标 密切相关。

        首先，先根据模式串求得next[ ]数组；
        然后，利用next[ ] 遍历文本串，求得模式串在文本串中出现了几次。

KMP匹配过程： 



class Solution {
public:
    int n1,n2;
    int next[500005];//存储最长公共前后缀的长度
    int kmp(string S, string T) {
        n1=S.size();
        n2=T.size();
        get_next(S);//获取模式串的next[]
        
        int res=0;
        int j=0;
        for(int i=0;i<n2;i++){//遍历文本串
            while(j>0&&T[i]!=S[j])
                j=next[j-1];
            if(T[i]==S[j])
                j++;
            if(j==n1){//如果模式串匹配结束，则出现次数+1
                res++;
                j=next[j-1];
            }
        }
        return res;
    }
    
    void get_next(string S){//获取模式串的next[]
        int j=0;
        next[0]=0;//初始化
        for(int i=1;i<n1;i++){//循环模式串
            while(j>0&&S[i]!=S[j]){
                j=next[j-1];
            }
            if(S[i]==S[j]){
                j++;
                next[i]=j;
            }
        }
    }
};


时间复杂度：
空间复杂度：