数据结构- KMP 算法_数据结构kmp算法

一、前言

• KMP 算法是由 D.E.Knuth ，J.H.Morris 和 V.R.Pratt 三位学者在 Brute-Force 算法的基础上提出的模式匹配改进算法，因此人们称它为克努特—莫里斯—普拉特操作（简称 KMP 算法）。KMP 算法的核心是利用匹配失败后的信息，尽量减少主串与字符串串的匹配次数以达到快速匹配的目的。具体实现就是通过一个 next() 函数实现，函数本身包含了模式串的局部匹配信息。KMP 算法的时间复杂度 O(m+n) 。
• Brute- Force 算法在模式串中有多个字符和主串中的若干个连续字符比较都相等，但最后一个字符比较不相等时，主串的比较位置需要回退。KMP 算法在上述情况下，主串位置不需要回溯，从而可以大大提高效率。

二、KMP 算法

1. 问题背景

• 如果我们有两个字符串，一个是长字符串 S ，另一个是短字符串 P ，这两个字符串中都只包含大小写英文字符和阿拉伯数字，现在我们要查找 P 在 S 中的位置，如果短字符串 P 在长字符串 S 中出现过，输出第一次出现的位置，否则输出 -1。
• 例如：长字符串 S = “ababababfab” ，短字符串 P = “ababf”，可以看出 P 在 S 中第一次出现位置是在S[4] 到S[8]，所以输出4。
• 例如：长字符串 S = “abababfab” ，短字符串 P = “ababg”，可以看出 P 在 S 中没有出现过，输出 -1。

2. 暴力匹配

2.1 暴力匹配过程

• 关于暴力匹配做法，我们依次比较长字符串各个字母为开头的字串是否与短字符串匹配。
• 依次比较以长字符串各个字母为开头的子串是否与短字符串匹配。
• 如果有匹配的输出起始位置，如果没有，输出 -1。
• 例如：以长的字符串 S = “ababababfab” ，短的字符串 P = “ababf” 为例，过程如下：
• 首先用S[0]开头的子串：ababa 与 P比较，不匹配。
• 接着用S[1]开头的子串：babab 与 P比较，不匹配。
• 接着用S[2]开头的子串：ababa 与 P比较，不匹配。
• 接着用S[3]开头的子串：babab 与 P比较，不匹配。
• 接着用S[4]开头的子串：ababf 与 P比较，匹配。输出4。

2.2 暴力匹配实现

• 首先我们假设，长字符串 S 匹配到 i 位置，短字符串 P 匹配到 j 位置。
• 如果当前字符串匹配成功（即 S[i] = P[j] ），则 i++ ， j++ ，继续匹配下一个字符。
• 如果当前字符串匹配失败（即 S[i] != P[j] ），则令 i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。因为 长字符串 S 当中 i - (j - 1) 位置之前的都与短字符串 P 进行对比过了，因此我们只需从该位置继续与短字符串 P 匹配即可。

int ViolentMatch(char* s, char* p)
{
	int sLen = strlen(s);
	int pLen = strlen(p);
 
	int i = 0;
	int j = 0;
	while (i < sLen && j < pLen)
	{
		if (s[i] == p[j])
		{
			i++;
			j++;
		}
		else
		{
			i = i - j + 1;
			j = 0;
		}
	}
	if (j == pLen)
	{
		return i - j;
	}		
	else
	{
		return -1;
	}		
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

3. KMP 算法

• 暴力匹配做法的优缺点都很明显，容易被我们想到，但时间复杂度较高。
• 因此，KMP 算法就是用来优化暴力算法，降低时间复杂度。

3.1 优化思路

• 此处，仍以长字符串 S = “ababababfab” ，短字符串 P = “ababf” 为例。
• 首先，用 S[0] 开头的字串：“ababa” 与 P = “ababf” 比较，比较到 S[4] 与 P[4] 的时候，S[4] != P[4]。

• 如果按照暴力匹配的思路，此时应该使用 S[1] 开头的字串 “babab” 与 P = "ababf“ 进行匹配。
• 这时，我们会发现，S[1~3] 与P[0~2] 不匹配，因此，以 S[1] 开头的字符串一定与 P 不匹配，便不需要进行以 S[1] 为开头字符串与 P 的比较了。

• 继续比较，我们又会发现，S[2~3] 与 P[0~1] 匹配，则以 S[2] 为开头的字符串在与 P = "ababf“ 进行匹配时，可以直接从 S[4] 与 P[2] 开始比较即可。比较到S[6] 与 P[4] 的时候，S[6] != P[4]。

• 继续比较，我们又会发现，S[3~5] 与 P[0~2] 不匹配，则以 S[3] 为开头的字符串在与 P = "ababf“ 一定匹配失败时，便不需要进行以 S[3] 为开头字符串与 P 的比较了。

-接下来用 S[4] 开头的子串： S[4] = “ababf“ 与 P = “ababf“ 比较。此时，由于 S[4~5] 与 P[0~2] 相同，那以S[4] 为开头的字符串与 P 匹配时，无需从S[4]开始，直接从S[5] 与 P[3] 开始比较即可。比较到S[8] 与 P[5] 的时候，S[8] = P[5]，字符串匹配完成，返回起始位置4。

• 总结一下，当出现了 S[i] != P[j] 时，我们进行检查： S[i-j+1 ~ i-1] 与 P[0 ~ j-2] 是否匹配，S[i-j+2 ~ i-1] 与 P[0 ~ j-3] 是否匹配······。也就是下图中 S 蓝色框里的子串与 P 蓝色框里的子串是否匹配，S 绿色框里的子串与 P 绿色框里的子串是否匹配，S 红色框里的子串与 P红色框里的子串是否匹配。

3.2 k 值

• 对上述实现过程进行总结，我们发现，只需要一个值 k ，k 是可以满足下面性质的最大值：
• 长字符串从 i-k 到第 i-1 的字符 S[i-k ~ i-1] 与短字符串前 k 个字符 P[0 ~ k-1] 相同。
• 对于大于 0 的 x:
• （1） 长字符串从 i-k-x 到第 i-1 的字符 S[i-k-x ~ i-1] 与短字符串前 k-x 个字符 P[0 ~ k+x-1] 不相同。
• （2） 长字符串从 i-k+x 到第 i-1 的字符 S[i-k+x ~ i-1] 与短字符串前 k-x 个字符 P[0 ~ k-x-1] 相同。
• 因为 k 是满足 P[0 ~ k-1] 与 S[i-k ~ i-1] 相同的最大值，所以 P[0 ~ k-1+x] 与 S[i-k-x ~ i-1] (x>0) 不同，因此以 S[i-k-x] 为开头的子串与 P 肯定不匹配。下次匹配，i 无需回溯到 i-k-x， 只需回溯到 i-k，j 回溯到 0。
• 因为 P[0 ~ k-1] 与 S[i-k ~ i-1] 相同，因此这一段无需比较。故 i 直接可以移动到回溯之前的位置，j 直接可以移动到 k 。
• 总结来看：当遇到不匹配的字符的时候，i 不往前移动，j 移动到 k 即可。

3.3 KMP 算法实现过程

• 此处，我们仍以长字符串 S = “ababababfab” ，短字符串 P = “ababf” 为例：
• 第一次出现字符不匹配的时候为：S[4] != P[4]。保证 P[0 ~ k-1] = S[4-k ~ 3] 的 k 的最大值为 2。
• 当 k = 4 时，匹配没有任何意义，k = 3 时，S[1] = b，与 P[0] 不相同，当 k = 2 时满足条件。

• 因为，k 的最大值为 2 ，S[1] 为开头的字符串，x = 1，所以 P[0 ~ 2+1-1] != S[2-1 ~ 3]， 即 P[0 ~ 2] != S[1 ~ 3]。因此以 S[1] 为开头的子串与 P 肯定不相同，无需进行后续比较。
• 接下来判断以 S[2] 为开头的字符串与 P 是否相同。又因为 P[0 ~ 1] = S[2 ~3]，所以转化为以 S[2] 为开头的字符串是否与 P 相同，只需要从 P[2] 与 S[4] 开始比较即可。i 之前的位置为 4，现在还是 4，相当于 i 没有回溯。j 之前的位置是 4 ，现在是 2 也就是 k 值，也没有回溯到 0。
• KMP 中的最长公共前后缀长度数组：next 。next[j] 含义是：P[j] 前面的字符串的最长公共前后缀长度。使得字符串有最长相等前后缀的前缀的最后一位的下标。
• 仍以长字符串 S = “ababababfab” ，短字符串 P = “ababf” 为例，P=“ababf” 的最长公共前后缀：
• P[0] 前面没有字符串，所以最长公共前后缀长度为 0。
• P[1] 前面的字符串为：a，a 没有前后缀 (前后缀长度要小于字符串长度) 。最长公共前后缀长度为 0。
• P[2] 前面的字符串为：ab，它的前缀为：a，后缀为b。前缀不等于后缀，所以没有公共前后缀，最长公共前后缀长度为 0。
• P[3] 前面的字符串为：aba，aba 的前缀有：a，ab， 后缀有：a，ba。因为 ab 不等于 ba，所以最长公共前后缀为 a，最长公共前后缀长度为 1。
• P[4] 前面的字符串为：abab，abab 的前缀有：a，ab，aba，后缀有：a，ab, bab。最长公共前后缀为 ab，长度为 2。
• 求 next 数组的过程：
• 初始化 next 数组，令 j = 0，i = 2，因为 next(1) = 0。
• 让 i 在 2 ~ len 范围内遍历，对每个 i ，执行 3、4，以求解 ne[i]。
• 直到 j 回退为 0，或是 p[i] = p[j + 1] 成立，否则不断令 j = ne[j]。
• 如果 p[i] = p[j + 1]，则 j = j + 1，之后，再将 j 赋值给 ne[i] 。

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;
    }
1
2
3
4
5
6
7
8
9
10
11
12

• 通过 next 数组有了最长公共前后缀，因此当我们前缀部分匹配失败后，可以直接从后缀开始下一步匹配过程，形成跳跃式匹配的高效模式。
• KMP 算法的具体实现过程及代码可见例题。

三、KMP 算法例题—— KMP 字符串

题目描述

给定一个字符串 S，以及一个模式串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模式串 P 在字符串 S 中多次作为子串出现。
求出模式串 P 在字符串 S 中所有出现的位置的起始下标。

输入格式

第一行输入整数 N，表示字符串 P 的长度。
第二行输入字符串 P。
第三行输入整数 M，表示字符串 S 的长度。
第四行输入字符串 S。

输出格式

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

数据范围

1 ≤ N ≤ 1e5
1 ≤ M ≤ 1e6

输入样例

3
aba
5
ababa

输出样例

0 2

具体实现

1. 模板

1.1 代码注解

• 在 C++ 当中，next 数组在某个头文件当中已经被使用过了，因此直接使用 next 数组时有可能会报错。
• j = ne[j]。 下次匹配的时候，直接移动到相同后缀部分。

1.2 实现代码

#include <bits/stdc++.h> 
using namespace std;

const int N = 100010, M = 1000010;

int n, m;
int ne[N];
char s[M], p[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;
    
    // 求ne过程 
    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;
    }
    
    // kmp匹配过程 
    for (int i = 1, j = 0; i <= m; i ++ )
    {
        while(j && s[i]!= p[j+1])  //如果不匹配 j表示退无可退了
        {
		   j = ne[j];   //表示j退几步
		}         
        if(s[i] == p[j+1])       //如果他俩已经匹配了
        {
		    j++;                 //就可以移动到下一个位置
        }
		if(j == n)                //匹配成功
        {
            cout << i-n << ' '; //i-n+1是下标, 但是题意从0开始, 所以还有减去1
            j = ne[j];
        }
    }
    system("pause"); 
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

2. 下标从0开始的写法（不建议）

2.1 实现代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1000010;

int n, m;
char s[N], p[N];
int ne[N];

int main()
{
    cin >> m >> p >> n >> s;

    ne[0] = -1;
    for (int i = 1, j = -1; i < m; i ++ )
    {
        while (j >= 0 && p[j + 1] != p[i])
		{
			j = ne[j];
		}
        if (p[j + 1] == p[i])
		{
			j ++ ;
		}
        ne[i] = j;
    }

    for (int i = 0, j = -1; i < n; i ++ )
    {
        while (j != -1 && s[i] != p[j + 1]) 
		{
			j = ne[j];
		}
        if (s[i] == p[j + 1]) 
		{
			j ++ ;
		}
        if (j == m - 1)
        {
            cout << i - j << ' ';
            j = ne[j];
        }
    }
    system("pause");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46