今天我们来讲一下kmp（看毛片）算法
讲到字符串操作有那些算法时，相信学过数据结构的小伙伴们都能想到kmp算法。
那么什么是kmp算法呢？从百度百科我们可以知道，kmp是三个人共同研究出来的一个算法，并以他们的名字命名。它的前身是Brute-Force算法，它有一个很大的缺点，那就是如果当前匹配失败那么指针往前移一位继续匹配。细心的小伙伴很容易就能发现匹配串越长的话本身就不容易匹配成功，那么你每次匹配失败指针只往前移动一位的话，其时间复杂度可想而知。那有没有什么更好的优化方式解决这一问题呢，kmp算法很好地解决了这一问题
初学kmp算法的小伙伴肯定会理解不来这个算法，其实这个算法还是不特别抽象并不是。当时我也是看了两三天才理解其中的奥秘。那废话不多说，我们就来看看这个kmp到底是怎么实现的吧
如果我们要了解kmp算法，那么我们应该先看看Brute-Force算法是怎么实现的，这个算法属于暴力算法。我们来看看具体怎么实现的吧
/*
*
* s为原串，p为模式串
*
*/
for(int i = 0; i <= s.size() - p.size(); i ++)
{
bool flag = true;
for(int j = 0; j < p.size(); j ++)
{
if(p[j] != s[i + j])
{
flag = false;
break;
}
}
if(flag) printf("pos : %d" , i);
}
从代码中我们可以发现这个算法的时间复杂度是 级别的，算法的实现不唯一，虽然这种写法看上去匹配失败时指针i并没有回退，但是我们要明白，两个字符串对比时，对应的指针是一直在改变的，如果匹配失败，那么指向原串s的指针就要指向本次匹配的第二个位置继续开始新的一次匹配，这样的话时间开销会非常大。
如果我们能够利用Brute-Force算法中的已知信息的话，那么我们是不是可以尝试优化呢，其实kmp算法巧妙地利用了最长前缀与后缀这一重要信息进行优化。
kmp算法的核心其实就是next数组的计算，也就是所谓的《部分匹配表》，里面存着前缀与后缀的最大相等长度。那何为前缀和后缀，前缀就是除第i个字符 p[i] 外的前i个字符组成的字串集合 ，后缀就是除第一个字符 p[1] 外，1-i中的字符组成的字串集合。部分匹配表 next[i] 存的就是i的前缀与后缀的最大公共元素（即最大共有元素的长度）。有了部分匹配表的话，在匹配失败时我们就知道到底需要往前回退多少就能继续往下匹配，而不是回退到本次匹配的下一个位置，这样就大大减少了匹配的时间开销。
那么我们来看看next数组是怎么计算的
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度，下标从1开始
求模式串的Next数组：
for(int i = 2 , j = 0; i <= m; i ++)
{
while(j && p[i] != p[j + 1]) j = ne[j];
if(p[i] == p[j + 1]) j ++;
ne[i] = j;
}
首先我们先手写一下部分匹配表的计算过程
以"ABCDABD"为例：
－ "A"的前缀和后缀都为空集，共有元素的长度为0；
－ "AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
－ "ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
－ "ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
－ "ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
－ "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；
－ "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。
if语句用于计数 next[i] 的值。由上述可以知道，如果 next[i - 1] 不为零，那么下一个位置是否出现新的字符，都可能导致 next[i] 为0（因为后缀一定会带上该字符）。所以我们计算时需要用到前面的匹配值进行回退，也就是while语句，如果当前j不为0并且匹配不相等时，往前退到与 next[j] 的值相等的位置（j回退），如果此时j不为0并且回退后 p[i] 依然不等于 p[j + 1]，那么就继续回退，直到j为0或者p[i] == p[j + 1] 为止。
简单来说就是p串自己与自己匹配，每次尝试 i 与 j+1 位的字符是否匹配，匹配的话 ne[i] 的值就是j的值（每次匹配时会检测j的值以及 p[i] 是否等于 p[j + 1] , 如果这两个条件同时满足，那么就需要回退，回退到当前j的 next[j] 上，如果next[j]不为0，那么是有可能存在前缀与后缀值相等，为0即第i位的next[i] = 0）。
例如："ABADABAC"
－ "A"的前缀和后缀都为空集，共有元素的长度为0；
－ "AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
－ "ABA"的前缀为[A, AB]，后缀为[BA, A]，共有元素为"A"，共有元素的长度1；
－ "ABAD"的前缀为[A, AB, ABA]，后缀为[BAD, AD, D]，共有元素的长度为0；
－ "ABADA"的前缀为[A, AB, ABA, ABAD]，后缀为[BADA, ADA, DA, A]，共有元素为"A"，长度为1；
－ "ABADAB"的前缀为[A, AB, ABA, ABAD, ABADA]，后缀为[BADAB, ADAB, DAB, AB, B]，共有元素为"AB"，长度为2；
－ "ABADABA"的前缀为[A, AB, ABA, ABAD, ABADA, ABADAB]，后缀为[BADABA, ADABA, DABA, ABA, BA, A]，共有元素为"ABA"，共有元素的长度为3。
－ "ABADABAC"的前缀为[A, AB, ABA, ABAD, ABADA, ABADAB, ABADABA]，后缀为[BADABAC, ADABAC, DABAC, ABAC, BAC, AC, C]，共有元素的长度为0。
上面这个例子，匹配最后一个字符的next[i]时，因为出现的字符导致 i 与 j + 1不匹配（此时i为8，j为3，next[j]为3），此时需要回退，回退到哪个位置由next[j]决定，当j为3时，它们依然不相等，所以最后 next[i] = j = 0;
注意
为了方便数组下标从1开始
前缀是指不包括第i的字符的连续字串集合，后缀是指不包括第1个的后i-1的连续字串集合（必需包括区间端点字符）
回退位数 = 已匹配位数 - next[j]， 用本模板的话就是
j = next[j]这行代码
模式串和原串匹配过程与next数组计算类似
既然我们知道了怎么计算next数组，那么就直接看代码吧
for(int i = 2 , j = 0; i <= n; i ++)
{
while(j && s[i] != p[j + 1]) j = ne[j];//回退
if(s[i] == p[j + 1]) j ++;
//j == m 代表匹配成功
if(j == m)
{
j = ne[j];//同样也是回退，因为p[j + 1] == '\0' != s[]的任何一个字符,所以提前让它回退，避免一些边界问题
//匹配成功后的逻辑
}
}
接下来我们做一道模板题好好理解一下这万恶的kmp算法吧
题目描述
给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串P在模式串S中多次作为子串出现。
求出模板串P在模式串S中所有出现的位置的起始下标。
输入格式
第一行输入整数N，表示字符串P的长度。
第二行输入字符串P。
第三行输入整数M，表示字符串S的长度。
第四行输入字符串S。
输出格式
共一行，输出所有出现位置的起始下标（下标从0开始计数），整数之间用空格隔开。
数据范围
输入样例：
3
aba
5
ababa
输出样例：
0 2
C++代码
#include <cstdio>
using namespace std;
const int N = 1e5 + 10 , M = 1e6 + 10;
int n , m;
char p[N] , s[M];
int ne[N];
int main()
{
scanf("%d%s%d%s" , &n , p + 1 , &m , s + 1);
for(int i = 2 , j = 0; i <= n; i ++)
{
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)
{
j = ne[j];
printf("%d " , i - n);
}
}
return 0;
}
引用
理解kmp的过程挺痛苦的，分享一下我看的那些文章吧
Alipay 
Wechat