字符串匹配问题之KMP算法

前言

阐述了问题:“在给定文本串S和模式串P的条件下,确定P在S中的位置”的通用算法。从暴力匹配法入手认识到其局限性,并给出KMP算法的中心思想、时间复杂度和代码实现。本文主要参考了文章:从头到尾彻底理解KMP

一、暴力匹配算法

算法思路为:
假设现在文本串S匹配到 i 位置,模式串P匹配到 j 位置,则有:

  • 如果当前字符匹配成功(即S[i] == P[j]),则i++,j++,继续匹配下一个字符;
  • 如果失配(即S[i]! = P[j]),令i = i - (j - 1),j = 0。相当于每次匹配失败时,i 回溯,j 被置为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
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++
i++;
j++;
}
else
{
//失配
i = i - j + 1;
j = 0;
}
}
//字符串匹配成功
if (j == pLen)
return i - j;
else
return -1;
}

二、KMP算法

暴力匹配法的不足在于过多的回溯没有必要,利用模式串前缀和后缀相同部分的信息,我们可以保持i不回溯,通过修改j的位置,让模式串尽量地移动到有效的位置。
当s[i] != p[j]时,s与p前面已匹配的部分是完全相同的,如果p的尾部(也是s匹配部分的尾部)和p的头部是完全相同的,那么前面相同的部分就不用再重复比较了,直接从不相同的部分开始比较。

我们采用next数组来记录模式串的前缀后缀信息,其每个元素的含义为:当前字符之前的字符串中,有多大长度的相同前缀后缀。例如next [j] = k,代表j之前的字符串中有最大长度为k的相同前缀后缀。

此也意味着在某个字符失配时,该字符对应的next 值会告诉你下一步匹配中,模式串应该跳到哪个位置(跳到next [j] 的位置)。如果next [j] 等于0或-1,则跳到模式串的开头字符,若next [j] = k 且 k > 0,代表下次匹配跳到j之前的某个字符,而不是跳到开头,且具体跳过了k个字符。下一次比较是s[i]和p[k]之间,而没必要s[i - (j - 1)]和p[0]之间。因为s[i-k]到s[i-1]与p[j-k]到p[j-1]与p[0]到p[k-1]相同,不需要再比较。

算法流程:
假设现在文本串S匹配到 i 位置,模式串P匹配到 j 位置

  • 如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++,继续匹配下一个字符;
  • 如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]。此举意味着失配时,模式串P相对于文本串S向右移动了j - next [j] 位。

代码实现:

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

三、next数组的构造

采用迭代的方式求得next数组,即已知next [0, …, j],求出next [j + 1]。

步骤如下:
对于P的前j+1个序列字符:

  • 若p[k] == p[j],则next[j + 1 ] = next [j] + 1 = k + 1;
  • 若p[k ] ≠ p[j],如果此时p[ next[k] ] == p[j ],则next[ j + 1 ] = next[k] + 1,否则继续递归前缀索引k = next[k],而后重复此过程。 相当于在字符p[j+1]之前不存在长度为k+1的前缀”p0 p1, …, pk-1 pk”跟后缀“pj-k pj-k+1, …, pj-1 pj”相等,那么是否可能存在另一个值t+1 < k+1,使得长度更小的前缀 “p0 p1, …, pt-1 pt” 等于长度更小的后缀 “pj-t pj-t+1, …, pj-1 pj” 呢?如果存在,那么这个t+1 便是next[ j+1]的值,此相当于利用已经求得的next 数组(next [0, …, k, …, j])进行P串前缀跟P串后缀的匹配。

如果pk != pj ,说明“p0 … pk-1 pk” ≠ “pj-k … pj-1 pj”。换言之,当pk != pj后,我们需要去寻找长度更短一点的相同前缀后缀。同时要注意的是:“p0 … pk-1” = “pj-k … pj-1”是前面迭代的结果。根据对称性,我们只需要拿p[next[k]] 去跟 pj 继续匹配,如果p[ next[k] ]跟pj还是不匹配,则需要寻找长度更短的相同前缀后缀,即下一步用p[ next[ next[k] ] ]去跟pj匹配。此过程相当于模式串的自我匹配,所以不断的递归k = next[k],直到要么找到长度更短的相同前缀后缀,要么没有长度更短的相同前缀后缀。如下图所示:

next数组构造

代码实现:

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
int KmpSearch(char* s, char* p)
{

void GetNext(char* p,int next[])
{
int pLen = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1)
{
//p[k]表示前缀,p[j]表示后缀
if (k == -1 || p[j] == p[k])
{
++k;
++j;
next[j] = k;
}
else
{
k = next[k];
}
}
}
}

此构造方法可以进一步优化。
不允许出现p[j] = p[ next[j] ]。因为当p[j] != s[i] 时,下次匹配必然是p[ next [j]] 跟s[i]匹配,如果p[j] = p[ next[j] ],必然导致后一步匹配失败(因为p[j]已经跟s[i]失配,p[j]与p[next[j]]相等,再去跟s[i]匹配必然失配),所以不能允许p[j] = p[ next[j ]]。如果出现了p[j] = p[ next[j] ]则需要再次递归,即令next[j] = next[ next[j] ]。
代码优化:

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
void GetNextval(char* p, int next[])
{
int pLen = strlen(p);
next[0] = -1;
int k = -1;
int j = 0;
while (j < pLen - 1)
{
//p[k]表示前缀,p[j]表示后缀
if (k == -1 || p[j] == p[k])
{
++j;
++k;
if (p[j] != p[k])
next[j] = k;
else
//p当出现[j] = p[ next[j ]]时需要继续递归,k = next[k] = next[next[k]]
next[j] = next[k];
}
else
{
k = next[k];
}
}
}

四、时间复杂度

如果某个字符匹配成功,模式串首字符的位置保持不动,仅仅是i++、j++;如果匹配失配,i 不变(即 i 不回溯),模式串会跳过匹配过的next [j]个字符。整个算法最坏的情况是,当模式串首字符位于i - j的位置时才匹配成功,算法结束。
所以,如果文本串的长度为n,模式串的长度为m,那么匹配过程的时间复杂度为O(n),算上计算next的O(m)时间,KMP的整体时间复杂度为O(m + n)。

您的支持是我创造源源不断地动力