背景介绍：
上述题目就是经典的KMP算法的模版题
首先我们介绍传统的暴力做法，不过显示是ac不了这道题的
暴力做法： 两个串依次比较
该算法的时间复杂度对于本题而言 就是O（mn）
如何优化呢？
对于下面这种情况而言：
当浅蓝色框内的部分匹配，A[5]!=B[4]时：
暴力做法 就是 A串 i=2 这个元素 与 B串首字母 重新进行匹配
显然 这个过程每次遇到不匹配的 都是A串向前一位 B串从头开始比较 非常繁琐
故这里 就有大佬创造了 KMP算法！！！！！！！！！！
其核心就是优化上述 过程
先简单解释一下 KMP算法 主要做了什么工作哈
a b串 黑色线之间部分已经匹配，后面一个元素（绿色圈里面的）不匹配
此时暴力做法就是：
a串向后移动一个位置，与b串从头开始比较，及也就是从紫线部分从头开始比较
KMP的思想就是，a串向后最多能移动几个位置，而保证不出错。
这里引入 最长 前缀 后缀 相等 的概念 （这里就不详细介绍了 帖子很多 也很简单 以下用数组ne[]表示）
首先证明 x的 存在且必要：
（这部分绿线长度为非负 >=0）即就是 不存在匹配的 前后缀的串
又因为黑色线之间的部分 a b串本身就是匹配的 故可以得到：
ZW这两部分 是匹配的
因为x是非负的 故一定存在
此时直接比较红色框内的这部分即可 因为前面已经是配的了
一次KMP在字符串匹配上面的效率很快 时间复杂度 O（n）！！！！！
以下这部分 重中之重！！！！！！！-
理解了 KMP算法的思想 下面主要就是求 ne数组 存储前后串匹配位置的数组即可
用到的方法就是 递推的方法
首先解释一下 ne数组 里面的数字表示啥： 假设ne[ j ]=k;
意思是： 数组下标 从 0 1 2 一直到 j的这部分 其 前缀 后缀 的长度为 k+1
有了这个概念 我们定义不匹配为 -1 表达式ne【j】=k； 且前缀后缀长度均小于其自身 即 k 所以已知 ne【0】= -1； 假设j=n时已知，ne【n】=x 红的括号内的两部分 匹配 即为前缀 后缀 字符串 （且为最长哈 定义保证了） 注释：其中 n x 为数组下标 且数组下标 从0开始 + 来计算j=n+1时 有点数学归纳法的意思了哈 这也是 为啥代码体现为 递推 这里就需要分情况讨论了： 第一种情况：arr【n+1】==arr【x+1】 此时ne【n+1】=x+1 结束 第二种情况：arr【n+1】!=arr【x+1】 此时就要自己去寻找 0~ n+1 下标是的 最长相等前后缀的位置了 暴力做法（为什么每次都要提到暴力做法，因为好的做法 都是从暴力做法去优化出来的！！！！） 首先看 挪一步 是否匹配： 挪动两步： ……………… 依次向下总到找到 ne【n+1】=y； y=-1,0,1,2……x 最大取到x嘛 这里范围也不重要 反正能找到就行了。 观察如下关系： A点坐标n c点坐标为x B点坐标为y-1 绿线与arr的三个焦点分别为1 2 3 注意 不是坐标哈 已知的ne【n】=x （我们的假设 别忘了） 所以：1A段与2C段是匹配的 又因为 ne【n+1】=y 所以：1A段与3B段是匹配的 所以2C段与3B段也是匹配的 所以这个东西出来 你们有什么感悟嘛 ！！ 是不是关系就得出来了： 即 B点是A点 不断ne【】 取出来的结果 结束条件就是arr【n+1】==arr【y】 当然了 y=-1的话 就是不存在这个点 （整个移到头就行） 当然了 也有找不到的情况： 就是到这 应该理解ne数组怎么求了 核心思想就是 递推 直到ne【0】 ne【1】 可以推出ne【2】……一直递推 //求Next数组 表示最长 相等前缀后缀字符串 for(int i=1,j=0;i<=n-1;++i) { while(j>0 && arr[i]!=arr[j] ) j=Next[j-1]+1; if( arr[i]==arr[j]) j++; Next[i]=j-1; } 解释一下： 因为ne【0】=-1 这是已知的 所以 i就从1 开始 也可以理解为上下要错开一个 代码不要从头开始 分析 只要记得 我们求 i这个位置时（求ne【i】） 前面 0~i-1 是已知的就行 这样方便初学者理解 所以这一步 就是我们上面提到的 结束条件有两个 找到了这两个点相等 或者就是没找到 因为没找到 ne【】=-1 所以j=0； 这个意思就是： 经过上面我找到了 他两匹配 是不是就要看下一位是不是匹配 所以j++了 因为i++ 会在循环条件里面判断 所以这里就不用多判断了 这里最后一步就是 因为上面我们找到了 ne【i】的值 所以来给他赋值 为什么减一呢 因为上面我们有个if 使得j++了 如果j=0 就是没找到 匹配的 所以赋值为-1； 看到这里ne数组就取出来了 最后就是 字符串的匹配过程： #include using namespace std; const int M=1000010; const int N=100010; char arr[N],brr[M]; int Next[N]; int main() { Next[0]=-1; int n,m; cin>>n; scanf("%s",arr); cin>>m; scanf("%s",brr); //求Next数组 表示最长 相等前缀后缀字符串 for(int i=1,j=0;i<=n-1;++i) { while(j>0 && arr[i]!=arr[j] ) j=Next[j-1]+1; if( arr[i]==arr[j]) j++; Next[i]=j-1; } //匹配过程 for(int i=0,j=0;i<=m-1;++i) { while(j>0 && brr[i]!=arr[j]) j=Next[j-1]+1; if( brr[i]==arr[j]) j++; if(j==n) { printf("%d ",i-n+1); j=Next[j-1]+1; } } return 0; } brr为 我们被搜索的 数组 arr为我们搜索的数组 匹配过程和 求ne完全类似 因为我们求ne其实就是 两个数组来做的 这里只不过就是两个数组不一样了 这里还是别从头分析 只要写出递推关系就行了 假设i-1 j-1 前面部分匹配 来看i j 两个位置 如果不相等 就一直取arr的 ne数组就行 直到这两个位置匹配 或者 没找到匹配的 如果匹配了 就直接就看下一个位置就行 这里的判断条件 就与上面求ne数组的地方不太一样 主要就是看我们arr的数组是不是匹配完了 下标都是从零开始 到n-1 这里为什么判断n呢 因为 上面的if条件 如果arr【n-1】匹配了 那就会使用j++ 所以会多一个 然后就是打印 brr匹配的起始下标 这里的下一步就是 接着搜索 首先来看一下暴力的话 这一步怎么写 for(int i=0,j=0;i<=m-1;++i) { while(j>0 && brr[i]!=arr[j]) j=Next[j-1]+1; if( brr[i]==arr[j]) j++; if(j==n) { printf("%d ",i-n+1); i=i-n+1; j=0; } } 就是 brr数组 从匹配位置的下一个点 和 arr从头开始 我们最开始的那个过程 怎么优化呢 画个图就明白了 这两部分已经匹配完成 下一部分匹配 无非就是这两种情况： 观察左边那一个 不就是 前后缀匹配 ne嘛 右边那一个不就是 ne到-1了么 所以这里就直接优化 就行 最后放一下 题目ac的截图吧 KMP算法 就我自己第一遍学习 编写了此博客 欢迎各位大佬批评指正 我是这么理解 KMP算法的 以及编写代码