题解 | #kmp算法#

KMP: 注意 next[0] = -1 是给外部排序第一个不想等的时候用的。

KMP PATTERTRN = 0, CUR =0 ;

PATTERN 和 模板大小一样的话（从0开始索引），就证明找到了一个，然后放入next从下一个开始匹配下一个。

Next 中 pre 从 -1 开始，cur要从0开始（从0开始索引）

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()||S.size()>T.size()){//边界处理
            return 0;
        }


        // next 数组初始化
        int res = 0, next[S.size()+1];
        next[0] = -1; // 从模式串的第一位开始匹配，文本串指向下一位。

        //标记为刚开始设置为-1，要处理从第一个元素开始匹配的情况
        for(int pre = -1, cur = 0; cur<S.size();){
            if(pre==-1||S[pre]==S[cur]){
                pre++;
                cur++;
                next[cur] = pre;
            }
            else pre = next[pre];
        }

       //KMP运算开始
        for(int pattern = 0, cur = 0; cur< T.size();){
            if(pattern==-1||S[pattern]==T[cur]){
                pattern++;
                cur++;

                if(pattern==S.size()){
                    res++;
                    pattern = next[pattern];
                }

            }else{
                pattern = next[pattern];
            }
        }


        return res;

    }
};