求C++ KMP算法-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

求C++ KMP算法

知与谁同 2018-07-18 16:29:07 805
急求 KMP算法, C++ 语言
算法 C++
分享到
取消 提交回答
全部回答(1)
  • 云篆
    2019-07-17 22:55:54
    const vector<int> * kmp_next(string &m) // count the longest prefex string ;
    {
    static vector<int> next(m.size());
    next[0]=0; // the initialization of the next[0];

    int temp; // the key iterator......

    for(int i=1;i<next.size();i++)
    {
    temp=next[i-1];

    while(m[i]!=m[temp]&&temp>0)
    { temp=next[temp-1];
    }

    if(m[i]==m[temp])
    next[i]=temp+1;
    else next[i]=0;

    }

    return &next;

    }

    bool kmp_search(string text,string m,int &pos)
    {
    const vector<int> * next=kmp_next(m);

    int tp=0;
    int mp=0; // text pointer and match string pointer;

    for(tp=0;tp<text.size();tp++)
    {
    while(text[tp]!=m[mp]&&mp)
    mp=(*next)[mp-1];

    if(text[tp]==m[mp])
    mp++;

    if(mp==m.size())
    { pos=tp-mp+1;
    return true;
    }
    }

    if(tp==text.size())
    return false;
    }
    0 0
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

推荐文章
相似问题
推荐课程