题解 | #kmp算法#

kmp算法

http://www.nowcoder.com/practice/bb1615c381cc4237919d1aa448083bcc

代码理解:

(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;
    }
    
};
全部评论

相关推荐

06-20 17:42
东华大学 Java
凉风落木楚山秋:要是在2015,你这简历还可以月入十万,可惜现在是2025,已经跟不上版本了
我的简历长这样
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务