[学习笔记]KMP算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[学习笔记]KMP算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1101字，纯文字阅读大概需要2分钟。

内容图文

第三次开 \(KMP\) 的坑，加油！

这是板子题：

P3375 【模板】KMP字符串匹配

这是板子：

#include<bits/stdc++.h>
using namespace std;
int j,kmp[1000005];
string s,p;
int main()
{
    cin>>s>>p;
    for(int i=1;i<p.length();i++)
    {
        while(j&&p[i]!=p[j]) j=kmp[j];
        kmp[i+1]=p[i]==p[j]?++j:0;
    }
    j=0;
    for(int i=0;i<s.length();i++)
    {
        while(j&&s[i]!=p[j]) j=kmp[j];
        j+=s[i]==p[j];
        if(j==p.length()) printf("%d\n",i-p.length()+2);
    }
    for(int i=1;i<=p.length();i++) printf("%d ",kmp[i]);
    return 0;
}

这是笔记：

1. \(kmp[i]\) 表示模式串第 \(i\) 位失配后，下面应该用模式串的第 \(kmp[i]\) 位继续进行匹配；
2. 初始化默认了 \(kmp[0]=kmp[1]=0\) ，这是因为如果第 \(0\) 或 \(1\) 位都失配了，就一定需要重头再来；
3. 初始化 \(kmp\) 数组时巧妙的三目运算符 kmp[i+1]=p[i]==p[j]?++j:0; 解决了特判问题；
4. \(kmp\) 数组匹配的过程相当于自己和自己匹配 （我配我自己） ；
5. \(i\) 是后缀的最后一位， \(j\) 是能匹配的前缀的最后一位，这就是为什么 \(j\) 可以循环使用，也是为什么得到的是 kmp[i+1] 而非 kmp[i] ，赋的值是++j 而非 j （第 \(i\) 位其实可以匹配到第 \(j\) 位）；
6. 输出的是 i-p.length()+2 是因为：(1) p.length() 没有取到最后一位；(2)字符串的第一位为 \(0\) 而非 \(1\) 。

结束~

内容总结

以上是互联网集市为您收集整理的[学习笔记]KMP算法全部内容，希望文章能够帮你解决[学习笔记]KMP算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---