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

        j=0;
        for(int i=0;i<T.size();i++){
            while(j>0&&S[j]!=T[i])j=ne[j-1];
            if(S[j]==T[i]){
                j++;
            }
            if(j==S.size()){
                ans++;
                j=ne[j-1];
            }
        }
        return ans;
    }
};

kmp本质在于next数组，这个数组储的是目标字符串每个字符位置的最长前后缀长度，当遇到给定的字符串和模板字符串的某个位置不匹配时，我就可以通过next数组的对应位置知道我要跳过几个字符在开始匹配，为什么可以跳过呢，因为前后缀，保证前面和后面相同这样就可以跳到那个中间不同的那个位置，再度开始往后匹配了；

那么next数组怎么求呢，这里呢kmp有两种不同的next数组表达方式，一种是next存储的是当不匹配时可以跳过的最长长度，一种是存储的是跳到位置的字符串的下标，这里展示的是第一种：有点类似于滑动窗口或者双指针的感觉，定义i跟j，i来遍历目标字符串（S），i可以看作是这个字符串的后缀末尾，j是字符串的前缀末尾，就像是两个指针i，j分别查找字符串的后缀和前缀，对于只有一个字符的这种情况，规定没有前后缀，所以初始化next【0】为0，然后i自然就从1开始遍历了，每次比较S[i]和S[j]，相等就j++看看有没有更长的部分，不等的话就只好将j往前回退，看看跟之前的字符拼一下能不能组成一个相等的字符串，当然并非回退一次，也可能需要回退多次，才能找到相同的，那怎么实现这个回退效果呢，我们知道j是前缀的末尾，那么是不是只要改变j的值就可以了？恰好next数组里就是需要最长的前后缀长度，也就是可以回退的距离，注意因为是长度的原因，所以next【j-1】才是正确的需要回退的值,可以通过一个模拟来自己来理解一下这里，然后j=next[j-1]这样就回退成功了，在前面的情况都通过后，最后别忘了next的赋值，对于以i这个字符结尾的后缀，存在的最长的前缀长度就是j，有next[i]=j；这样next数组就算是彻底构造成功了；

至于最后匹配S跟T的过程其实跟next是很像的，只不过是遍历S跟T，这里i跟j意义很简单，就是分别遍历两个字符串即可。不匹配的话就移动遍历S的那个指针j，跳到next里面指定的那个位置注意是j-1的下标，在从此位置开始遍历，当我们发现这个指针到达了S的终点代表出现了一次，记录答案，但并不意味结束，因为可能存在其他位置的答案，所以我们依然继续跳，继续匹配；知道遍历完T后结束程序；