KMP算法自我理解和模板

2021-05-23 19:30

阅读：599

标签：ace 模板 cin const bcd bsp using names 算法

字符串 abcd abc abcd abc

匹配串 cdabcd

匹配串的 next 0 0 0 0 1 2；

开始匹配

abcd abc abcd abc

cd abc d

a,d 匹配失败

next 数组进行移动

abcd abc abcd abcd

c dabcd

再次匹配

模板

#includeusing namespace std;
const int maxn=1e5+10;
int nt[1000];
//  next 数组首位为  0
int KMP(string ss,string tt)
{
    nt[0]=0;
    for(int p=1,k=0;p)
    {
        while(k>0 && tt[k]!=tt[p])
            k=tt[k-1];
        if(tt[k]==tt[p])
            k++;
        nt[p]=k;
    }  // 构建 next 数组
    for(int p=1,k=0;p)
    {
        while(k>0&& ss[p]!=tt[k])
            k=tt[k-1];
        if(ss[p]==tt[k])
            k++;
        if(k==tt.size())
        {
            cout"数组下标开始"1"   "endl;
            return 1;
        }
    }
    return 0;
}
int main()
{
    string ss,tt;
    cin>>ss>>tt;
    coutendl;
}

KMP算法自我理解和模板

标签：ace 模板 cin const bcd bsp using names 算法

原文地址：https://www.cnblogs.com/Andromeda-Galaxy/p/9734342.html

上一篇：【计算机算法设计与分析】——选择问题

下一篇：介绍三种PHP加密解密算法

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：KMP算法自我理解和模板
文章链接：http://soscw.com/index.php/essay/88349.html

亲，登录后才可以留言！

KMP算法自我理解和模板

评论

热门文章

推荐文章

最新文章

置顶文章

KMP算法自我理解 和 模板

评论

热门文章

推荐文章

最新文章

置顶文章

KMP算法自我理解和模板