KMP算法

对于常规的KMP字符串匹配算法加以改进即可。
代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    int kmp(string S, string T) {
        // write code here
        if(S.empty()||T.size()>T.size()) return 0;//对于边界条件的判断
        int res=0;//用于结果的返回
        int i=1,j=0;
        int next[S.size()];//首先求next数组，用于保存当字符串失配时模板串应该回退的指针值
        next[1]=0;//规定next[0]=1,
        while(i<S.length()){//求解，即字符串的最大相等前后缀长度
            if(j==0||S[i]==S[j]){
                ++i;++j;//若Pi=Pj则next[j+1]=next[j]+1
                next[i]=j;
            }
            else
                j=next[j];//否则，令j=next[j],循环继续
        }
        int k=1,l=1;
        while(k<=T.length()&&l<=S.length()){//KMP算法主体
             if(l==0||T[k]==S[l]){
                 ++k;++l;//继续比较后继字符串
             }
            else
                l=next[l];//失配时，模式串向右移
            if(l==S.length()){//改进之处在于，此时加个计数值
                res+=1; 
            }
        }
        return res;
    }
};