算法学习系列（十一）：KMP算法

引言

这个KMP算法就是怎么说呢，就是不管算法竞赛还是找工作笔试面试，都是非常爱问爱考的，其实也是因为这个算法比较难懂，其实就是很难，所以非常个人的一个思维逻辑吧，反正就是用来区分人的，我会你不会，那么我就比你牛逼，所以那就开始吧。

一、算法概念

这个KMP算法就是用来匹配字符串的，在一个字符串中是否有另一个字符串的存在，如果存在返回原始字符串中的初始下标

二、题目描述

给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。模式串 P 在字符串 S 中多次作为子串出现。求出模式串 P 在字符串 S 中所有出现的位置的起始下标。输入格式
第一行输入整数 N，表示字符串 P 的长度。
第二行输入字符串 P。
第三行输入整数 M，表示字符串 S 的长度。
第四行输入字符串 S。输出格式
共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。数据范围
1≤N≤105，1≤M≤106输入样例：
3
aba
5
ababa输出样例：
0 2

三、思路讲解

这个KMP最重要的就是一个next数组，先来说一下这个是什么意思吧，next [i] 里面存的是在模板串中的以第i号下标为终点，和以第1号下标为起点的两个字符串相等的话，它们的长度最长为 j ，也就是第 i 号位置的最大的后缀和前缀相等的最大长度是j

然后就是匹配算法了，如下图如果说在模板串中，到第 j 号下标都匹配成功的话，原串的第 i 号下标和模板串的第 j+1号下标不匹配了，那么最暴力的做法就是将模板串往后移动一位，再重新一个一个匹配，那么KMP的想法是，我之前已经匹配了那么些串了，那么能不能用一些性质，来帮助我更加高效的匹配呢

然后又因为绿色的都是相等的，又因为我们有了next数组，可以知道当前的模板串往后移动的话，可以知道向后移动的最小距离是多少，又能够使得从 [1, ne[j] ]的模板串跟从 [i - j + 1, i - 1]的字串是相等的， 也就是说能使每一次匹配的原串没有浪费，都不用再重新匹配

三、代码实现

然后这个KMP的话，下标一般是从1开始的

#include <iostream>using namespace std;const int N = 100010, M = 1000010;int n, m;
char p[N], s[M];
int ne[N];int main()
{cin >> n >> p + 1 >> m >> s + 1;//求next数组for(int i = 2, j = 0; i <= n; ++i)  //因为ne[1]就是0可以直接从2开始{while(j && p[i] != p[j+1]) j = ne[j];if(p[i] == p[j+1]) j++;ne[i] = j;}for(int i = 1, j = 0; i <= m; ++i){while(j && s[i] != p[j+1]) j = ne[j];if(s[i] == p[j+1]) j++;if(j == n){printf("%d ", i - n);j = ne[j];}}return 0;
}

四、测试