文章和代码曾经归档至【Github仓库：https://github.com/timerring/algorithms-notes 】或者公众号【AIShareLab】回复 算法笔记 也可获取。

KMP

KMP算法，又称模式匹配算法，可能在线性工夫内断定字符串 A[1\~N]是否为字符串B[1\~M]的子串，并求出字符串A在字符串B中各次呈现的地位。

例题：

给定一个字符串 S，以及一个模式串 P，所有字符串中只蕴含大小写英文字母以及阿拉伯数字。

模式串 P 在字符串 S 中屡次作为子串呈现。

求出模式串 P 在字符串 S 中所有呈现的地位的起始下标。

输出格局

第一行输出整数 N，示意字符串 P 的长度。

第二行输出字符串 P。

第三行输出整数 M，示意字符串 S 的长度。

第四行输出字符串 S。

输入格局

共一行，输入所有呈现地位的起始下标（下标从 0 开始计数），整数之间用空格隔开。

数据范畴

$1≤N≤10^5$
$1≤M≤10^6$

输出样例：

3aba5ababa

输入样例：

0 2

最奢侈的做法(暴力做法)

S[N]-- source串(长), P[N]---pattern串(短);for(int i = 0; i < n; i++){    bool flag = true;    for(int j = 0; j < m; j++)        if(S[i + j - 1] != P[j])        {            flag = false;            break;        }}

KMP算法

首先用一个例子模仿KMP过程。

原数组为s，匹配数组为p。

首先求解next数组。**next记录的就是以后作为后缀末位的j对应的前缀末位的地位。**总结来说next[i] 就是使子串 s[0…i] 有最长 相等前后缀 的前缀的最初一位的下标。（next[i] 示意使字串 s[0…i] 中前缀 s[0…k] 等于后缀 s[i-k…i] 的最大的 k。如果找不到相等的前后缀，就令 next[i] = -1。显然，next[i] 就是所求最长相等 前后缀中 前缀的最初一位的下标。）

例如：abababaabnext[0] = -1next[1] = -1next[2] = 0next[3] = 1next[4] = 2next[5] = 3next[6] = 4next[7] = 0next[8] = 1

同时，next数组不能是自身，因为如果是自身，则通过next数组跳过该整个字符串，从最开始从新比拟就没有意义了。

通常应用next[N]可能会和头文件中抵触，因而采纳ne[N]记录。求next的过程相似于一个本人和本人匹配的过程。
// p[0...0] 的区间内肯定没有相等前后缀ne[0] = -1;// 结构模板串的 next 数组 从1开始即可for (int i = 1, j = -1; i < n; i ++){    // 若前后缀匹配不胜利，重复令 j 回退，直至到 -1 或是 s[i] == s[j + 1]    while (j != -1 && p[i] != p[j + 1]) j = ne[j];    if (p[i] == p[j + 1]) j ++; // 匹配胜利时，最长相等前后缀变长，最长相等前后缀最初一位变大    ne[i] = j; // 令 ne[i] = j，以不便计算 next[i + 1]}

接下来进入 kmp，kmp 算法照葫芦画瓢，给定一个文本串 text 和一个模式串 pattern，而后判断模式串 pattern 是否是文本串 text 的子串。

以 text = “abababaabc”、pattern = “ababaab” 为例。令 i 指向 text 的以后欲比拟位，令 j 指向 pattern 中以后已被匹配的最初位，这样只有 text[i] == pattern[j + 1] 成立，就阐明 pattern[j + 1] 也被胜利匹配，此时让 i、j 加 1 持续比拟，直到 j 达到 m - 1(m 为 pattern 长度) 时阐明 pattern 是 text 的子串。在这个例子中，i 指向 text[4]、j 指向 pattern[3]，表明 pattern[0…3] 曾经全副匹配胜利了，此时发现 text[i] == pattern[j + 1] 成立，这阐明 pattern[4] 胜利匹配，于是令 i、j 加 1。

始终比拟的是s[i]与p[j+1]是否匹配。

当text[5] != pattern[4 + 1]，匹配失败。为了不让 j 间接回退到 -1，应寻求回退到一个离以后的 j （此时 j 为 4）最近的 j’，使得 text[i] == pattern[j’ + 1] 可能成立，并且 pattern[0…j’] 依然与 text 的相应地位处于匹配状态，即 pattern[0…j’] 是 pattern[0…j] 的后缀。这很容易令人想到之前的求 next 数组时碰到的相似问题。答案是 pattern[0…j’] 是 pattern[0…j] 的最长相等前后缀。也就是说，只须要一直令 j = next[j]，直到 j 回退到 -1 或者是 text[i] == pattern[j + 1] 成立，而后持续匹配即可。**next 数组的含意就是当 j + 1 位失配时，j 应该回退到的地位。**对于刚刚的例子，当 text[5] 与 pattern[4 + 1] 失配时，令 j = next[4] = 2，而后咱们会发现 text[i] == pattern[j + 1] 可能成立，因而就让它持续匹配，直到 j == 6 也匹配胜利，这就意味着 pattern 是 text 的子串。

KMP算法过程：

for (int i = 0, j = -1; i < m; i ++){    while (j != -1 && s[i] != p[j + 1]) j = ne[j]; // 匹配不胜利    if (s[i] == p[j + 1]) j ++; // 匹配胜利时，模板串指向下一位    if (j == n - 1) // 模板串匹配实现，第一个匹配字符下标为 0，故到 n - 1    {        // 匹配胜利时，文本串完结地位减去模式串完结地位即为起始地位（能够通过上图得悉）        cout << i - j << ' ';        // pattern串在source串中呈现的地位可能是重叠的，        // 须要让 j 回退到肯定地位，再让 i 加 1 持续进行比拟        // 回退到 ne[j] 能够保障 j 最大，即曾经胜利匹配的局部最长        // 本人模仿一下：source:acababab和pattern:acab或者source:abababab和pattern:abab即可了解        j = ne[j];     }}

记住next数组永远是针对j，即pattern串操作的。

工夫复杂度：

工夫复杂度是O(n+m)，这里while最多执行m次，j最多加m次。总共执行次数是O(2m)次。

整个 for 循环中 $\mathrm{i}$ 是一直加1的，所以在整个过程中 $\mathrm{i}$ 的变动次数是O(m) 级别，接下来思考 $\mathrm{j}$ 的变动，咱们留神到 $\mathrm{j}$ 只会在一行中减少，并且每次只加1，这样在整个过程中 $\mathrm{j}$ 最多减少m次；而其它状况 $\mathrm{j}$ 都是一直减小的，因为 $\mathrm{j}$ 最小不会小于 -1 ，因而在整个过程中, j 最多只能缩小 m 次。也就是说 while 循环对整个过程来说最多只会执行 $\mathrm{m}$ 次，因而 $\mathrm{j}$ 在整个过程中变动次数是 O(m) 级别的。因为 $\mathrm{i}$ 和 $\mathrm{j}$ 在整个过程中的变动次数都是 O(m) ，因而 for 循环局部的整体复杂度就是 O(m) 。计算 next 数组须要 O(n) 的工夫复杂度(分析方法上同)，因而 kmp 算法总共须要 O(n+m) 的工夫复杂度。

code

#include <iostream>using namespace std;const int N = 1000010;char p[N], s[N]; // 用 p 来匹配 s// “next” 数组，若第 i 位存储值为 k// 阐明 p[0...i] 内最长相等前后缀的前缀的最初一位下标为 k// 即 p[0...k] == p[i-k...i]int ne[N]; int n, m; // n 是模板串长度 m 是模式串长度int main(){    cin >> n >> p >> m >> s;    // 本人不能是本人的前后缀    ne[0] = -1;    // 结构pattern串的 next 数组    for (int i = 1, j = -1; i < n; i ++)    {        // 若前后缀匹配不胜利，重复令 j 回退，直至到 -1 或是 s[i] == s[j + 1]        while (j != -1 && p[i] != p[j + 1]) j = ne[j];        if (p[i] == p[j + 1]) j ++; // 匹配胜利时，最长相等前后缀变长，最长相等前后缀最初一位变大        ne[i] = j; // 令 ne[i] = j，以不便计算 next[i + 1]    }    // KMP    for (int i = 0, j = -1; i < m; i ++)    {       while (j != -1 && s[i] != p[j + 1]) j = ne[j]; //匹配失败，回溯       if (s[i] == p[j + 1]) j ++; // 匹配胜利       if (j == n - 1) // n是pattern串的长度       {           // 匹配胜利时，文本串完结地位减去模式串长度即为起始地位           cout << i - j << ' ';           j = ne[j];        }    }   return 0;}