题解 | #kmp算法#

kmp算法

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

#include <cstdio>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    void compute_next(string s,vector<int> &next,int size){
        int j=0;
        int i=1;
        while(i<size){
            if(j==0 || s[i]==s[j]){
                next[++i]=++j;
                //cout<<next.size()<<" "<<i<<endl;
            }else{
                j=next[j];
            }
        }
        return;
    }
    int kmp(string S, string T) {
        // write code hereS
        unsigned int size_S=S.size();
        unsigned int size_T=T.size();
        vector<int> next;
        //cout<<size_S<<endl;
        next.resize(size_S+1,0);
        compute_next(S, next, S.size());
        //cout<<next[size_s]<<endl;
        int i=0;
        int j=0;
        int result=0;

        while(i<size_T){

            if(j==0 || S[j] == T[i]){
                j++;
                i++;
            }else{
                
                j=next[j];
            }
            if(j==size_S){
                result++;
                j=next[j];

            }
        }

        return result;
    }
};

全部评论

相关推荐

07-11 15:12
门头沟学院 Java
别人在上班,我就在工位上看看视频啥的,这正常吗?
程序员小白条:实习就是摸鱼,只是公司指标,把你进来了,可能那时候客户很多,但等你进来的时候,已经是淡季了,根本没多少需求,或者说根本不适合实习生去完成,因此你就每天干坐着就行,可能1,2个月都没需求
实习生的蛐蛐区
点赞 评论 收藏
分享
07-07 17:06
已编辑
深圳技术大学 golang
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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