题解 | #kmp算法#

代码理解：

（1）算法思想：http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

（2）如何生成next数组：https://www.bilibili.com/video/BV16X4y137qw?from=search&seid=11962705200133341346&spm_id_from=333.337.0.0

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    int kmp(string S, string T) {
        // write code here
        int m = S.length(), n = T.length();
        if(m > n || n == 0){
            return 0;
        }
        
        int count = 0;
        vector<int> next = get_next(S);
        for(int i=0,j=0; i<n; i++){
            while(j>0 && T[i] != S[j]){
                j = next[j-1];
            }
            if(T[i] == S[j]){
                j++;
            }
            if(j == m){
                count += 1;
                j = next[j-1];
            }
        }
        
        return count;
    }
    
    vector<int> get_next(string S){
        int n = S.length();
        vector<int> next(n);
        for(int i=1, j=0; i<n; i++){
            while(j>0 && S[i] != S[j]){
                j = next[j-1];
            }
            if(S[i] == S[j]){
                j++;
            }
            next[i] = j;
        }
        return next;
    }
    
};