【专题】KMP

简介

Knuth-Morris-Pratt字符串查找算法,简称为“KMP算法”,常用于在一个文本串S内查找一个模式串T的出现位置。这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表,故取这3人的姓氏命名此算法。时间复杂度O(|S|+|T|)。

朴素算法

给出一个最为常见的朴素字符串模式匹配算法,枚举文本串S的每一位,作为起点与模式串T进行匹配。时间复杂度O(|S|*|T|)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int simple(char* s, char* t, int n, int m)
{
int i = 0, j = 0;
while (i < n)
{
if (s[i] == t[j]) {
i++, j++;
if (j >= m) { // 匹配成功
return i-j;
}
} else {
i = i-j + 1;
j = 0;
}
}
return -1;
}

朴素算法的运行过程如下:

暴力匹配

注意到,如下图,枚举以S[1]为起点,匹配到最后一个字符,S[4]!=T[3],失配之后朴素做法是指针回退,以S[2]为起点开始下一轮匹配,即i=i-j+1, j=0。

冗余

毫无疑问,随着文本串S的长度增加,每一次回退重新匹配会花费大量的时间。那么有没有办法优化呢?

next数组

通过分析模式串T可以得到next数组,也可以当作fail数组理解。对于模式串T="abac",当匹配到'c'时失配了,那么说明前面的"aba"已经匹配成功,"aba"最长的相等前缀后缀(不包括本身)'a',那么失配'c'后,我们可以跳过s[3]='a'(文本串S"aba"的后缀)与T[0]='a'(模式串T"aba"的前缀),直接匹配S[4]='b'T[0]='b'

next

为什么是最长的、相等的、不包括本身的前缀后缀呢?看下图自行理解。

前缀后缀

由下表可以看出最长相等前缀后缀整体右移,首位加上-1,即是next数组。

模式串abac
最长相等前缀后缀0010
next数组-1001

next数组优化

对于失配时S[4]='c'T[3]='b'不相等,由T[1]='b'T[3]='b'相等,得出T[1]='b'S[4]='c'也不相等,我们可以跳过这一步匹配。

next优化

注意C++中next是关键字(迭代器的一个函数),以及字符串下标从0开始从1开始的代码稍有不同,注意必须求到next[|T|],求字符串匹配数量以及最小循环节都需要用到。下面给出的是字符串下标从0开始的next数组的一种求法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int nxt[mxn];

void getnxt(char* t, int m)
{
int i = 0, j = -1; nxt[0] = -1;
while (i < m)
{
if (j == -1 || t[i] == t[j]) {
i++, j++;
// if (t[i] == t[j])
// nxt[i] = nxt[j]; // next数组优化
// else
nxt[i] = j;
} else
j = nxt[j];
}
}

KMP算法

有了next数组,下面给出KMP算法代码,与朴素算法类似,但是i不用回退了,可以看出求next数组的过程也是一个模式串T与自身匹配的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int KMP(char* s, char* t, int n, int m)
{
int i = 0, j = 0, ans = 0;
while (i < n)
{
if (j == -1 || s[i] == t[j]) {
i++, j++;
if (j >= m) { // 匹配成功
return i-j;
}
} else
j = nxt[j];
}
return -1;
}

KMP算法的运行过程如下:

KMP

最小循环节

参考 KMP模板,最小循环节

定理:

假设S的长度为len,则S存在最小循环节,循环节的长度L为len-next[len],子串为S[0…len-next[len]-1]。 (1)如果len可以被len-next[len]整除,则表明字符串S可以完全由循环节循环组成,循环周期T=len/L。 (2)如果不能,说明还需要再添加几个字母才能补全。需要补的个数是循环个数L-len%L=L-(len-L)%L=L-next[len]%L,L=len-next[len]。

index01234567
charabcdabc
next-10000123

为方便说明,先设字符串的长度为len,循环子串的长度为L

例1 s0s1s2s3s4s5,next[6]=3 即s0s1s2=s3s4s5 很明显可知:循环子串为s0s1s2,L=len-next[6]=3,且能被len整除。

例2 s0s1s2s3s4s5s6s7,next[8]=6 此时len-next[8]=2,即L=2 由s0s1s2s3s4s5=s2s3s4s5s6s7 可知s0s1=s2s3,s2s3=s4s5,s4s5=s6s7 显然s0s1为循环子串

例3 s0s1s2s3s4s5s6,next[7]=4 此时len-next[7]=3,即L=3 由s0s1s2s3=s3s4s5s6 可知s0s1=s3s4,s2s3=s5s6 从而可知s0s1s2=s3s4s5,s0=s3=s6 即如果再添加3-4%3=2个字母(s1s2),那么得到的字符串就可以由s0s1s2循环3次组成

对于一个字符串,如abcd abcd abcd,由长度为4的字符串abcd重复3次得到,那么必然有原字符串的前八位等于后八位。也就是说,对于某个下标从0开始的字符串S,长度为len,由长度为L的字符串s重复R次得到,当R≥2时必然有S[0…len-L-1]=S[L…len-1]。

那么对于KMP算法来说,就有next[len]=len-L。此时L肯定已经是最小的了(因为next的值是前缀和后缀相等的最大长度,即len-L是最大的,那么在len已经确定的情况下,L是最小的)

模板

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
48
49
50
char s[mxn], t[mxn];
int nxt[mxn];

void getnxt(char* t, int m)
{
int i = 0, j = -1; nxt[0] = -1;
while (i < m)
{
if (j == -1 || t[i] == t[j]) {
i++, j++;
// if (t[i] == t[j])
// nxt[i] = nxt[j]; // next数组优化
// else
nxt[i] = j;
} else
j = nxt[j];
}
}

int KMP(char* s, char* t, int n, int m)
{
int i = 0, j = 0, ans = 0;
while (i < n)
{
if (j == -1 || s[i] == t[j]) {
i++, j++;
if (j >= m) {
// ans++;
// j = nxt[j];
return i-j;
}
} else
j = nxt[j];
}
// return ans;
return -1;
}

int main()
{
scanf("%s %s", s, t);
getnxt(t, strlen(t));
for(int i=0; i<strlen(t); i++){
printf("%d ", nxt[i]);
}
printf("\n");
printf("%d\n", simple(s, t, strlen(s), strlen(t)));
printf("%d\n", KMP(s, t, strlen(s), strlen(t)));
return 0;
}