关于算法:KMP算法详解

文章和代码曾经归档至【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$

输出样例 ：

3
aba
5
ababa

输入样例 ：

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] 就是所求最长相等 前后缀中 前缀的最初一位的下标 。）

 例如：abababaab
next[0] = -1
next[1] = -1
next[2] = 0
next[3] = 1
next[4] = 2
next[5] = 3
next[6] = 4
next[7] = 0
next[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;
}