字符串匹配的 KMP算法

一般字符串匹配过程

KMP算法是字符串匹配算法的一种改进版,一般的字符串匹配算法是:从主串(目标字符串)模式串(待匹配字符串)的第一个字符开始比较,如果相等则继续匹配下一个字符, 如果不相等则从主串的下一个字符开始匹配,直到模式串被匹配完,则匹配成功,或主串被匹配完且模式串未匹配完,则匹配失败。匹配过程入下图:

字符串匹配的 KMP算法

这种实现方式是最简单的, 但也是低效的,因为第三次匹配结束后的第四次和第五次是没有必要的

分析

第三次匹配在j = 0(a)i = 2(a)处开始,在j = 4(c)i = 6(b)处失败,这意味着模式串和主串中:j = 0(a)i = 2(a)j = 1(b)i = 3(b)j = 2(c)i = 4(c)j = 3(a)i = 5(a)这四个字符相互匹配。

分析模式串的前3个字符:模式串的第一个字符j = 0是aj = 1(b)j = 2(c)这两个字符和j = 0(a)不同,因此以这两个字符开头的匹配必定失败,在第三次匹配中,主串中i = 3(b)i = 4(c)和模式串j = 1(b)j = 2(c)相互匹配,因此匹配失败后,可以直接跳过主串中i = 3(b)i = 4(c)这两个字符的匹配。

继续分析模式串的j = 3(a)j = 4(c)这两个字符,如果模式串匹配到j = 4(c)这个字符才失败的话,因为j = 4(c)的前一个字符j = 3(a)和第一个字符j = 0(a)是相同的,结合上一个分析得知:

1):下一次匹配中主串已经跳过了和j = 3(a)前两个相互匹配的字符i = 3(b)i = 4(c),将从i = 5(a)开始匹配。 
2):j = 3(a)i = 5(a)相互匹配。

因此下一次匹配认为j = 3(a)i = 5(a)已经匹配过了,匹配从j = 4(b)i = 6(b)开始,这样的话也跳过了j = 3(a)这个字符的匹配。

同理可得第二次匹配也是没必要的。

KMP算法

KMP算法匹配过程

利用KMP算法匹配的过程如下图:

字符串匹配的 KMP算法

KMP算法的改进之处在于:能够知道在匹配失败后,有多少字符是不需要进行匹配可以直接跳过的,匹配失败后,下一次匹配从什么地方开始能够有效的减少不必要的匹配过程。

next[n]求解方法

由上面的分析可以发现,KMP算法的核心在于对模式串本身的分析,其分析结果能提供在j = n位置匹配失败时,从j = 0j = n - 1这个子串中前缀和后缀的最长公共匹配的字符数,这样说可能比较难以理解,看下图:

字符串匹配的 KMP算法

在得到子串前缀和后缀的最长公共匹配字符数l后,以后在i = x,j = n处匹配失败时,可以直接从i = x,j = l处继续匹配(证明过程参考:严蔚敏的《数据结构》4.3章),这样问题就很明显了,我们要求出n和l对应的值,其中n是模式串字符数组的下标,l的有序集合通常称之为next数组,前面两个模式串的next数组下标n的对应如下:

字符串匹配的 KMP算法

模式串2完整匹配过程

有了这个next数组,那么在匹配的过程中我们就能在j = n处匹配失败后,根据next[n]的值进行偏移,其中next[0]固定为-1,代表在当前i这个位置整个模式串和主串都无法匹配成功,要从下一个位置i = i + 1j = 0处开始匹配,模式串2的匹配过程如下:

字符串匹配的 KMP算法

现在知道了next数组的作用,也知道在有next数组时的匹配过程,那么剩下的问题就是如何通过代码求出next数组匹配过程了。

next数组的过程可以认为是将模式串拆分成n个子串,分别对每个子串求前缀和后缀的最长公共匹配字符数l,这一点可以通过上图(最长公共匹配字符数)看出来(没有画出l=0时的图解)看出来。

代码实现

next数组的代码如下:

 void get_next(string pattern, int next[]) {
// !!!!!!!!!!由网友(评论第一条)指出该算法存在问题,已将有问题的代码注释并附上临时想到的算法代码。 // int i = 0; // i用来记录当前计算的next数组元素的下标, 同时也作为模式串本身被匹配到的位置的下标
// int j = 0; // j == -1 代表从在i的位置模式串无法匹配成功,从下一个位置开始匹配
// next[0] = -1; // next[0]固定为-1
// int p_len = pattern.length();
// while (++i < p_len) {
// if (pattern[i] == pattern[j]) {
// // j是用来记录当前模式串匹配到的位置的下标, 这就意味着当j = l时,
// // 则在pattern[j]这个字符前面已经有l - 1个成功匹配,
// // 即子串前缀和后缀的最长公共匹配字符数有l - 1个。
// next[i] = j++;
// } else {
// next[i] = j;
// j = 0;
// if (pattern[i] == pattern[j]) {
// j++;
// }
// }
// } int j = ;
next[] = -;
int p_len = pattern.length();
int matched = ;
while (++j <= p_len) {
int right = j - ;
int mid = floor(right / );
int left = right % == ? mid - : mid;
int curLeft = left;
int curRight = right;
while (curLeft >= ) {
if (pattern[curLeft] == pattern[curRight]) {
matched++;
curLeft--;
curRight--;
} else {
matched = ;
curLeft = --left;
curRight = right;
}
}
next[j] = matched;
matched = ;
}
}

根据next数组求模式串在主串中的位置代码如下:

int search(string source, string pattern, int next[]) {
int i = ;
int j = ;
int p_len = pattern.length();
int s_len = source.length();
while (j < p_len && i < s_len) {
if (j == - || source[i] == pattern[j]) {
i++;
j++;
}
else {
j = next[j];
}
}
if (j < pattern.length())
return -;
else
return i - pattern.length();
}

测试代码如下:

int main() {
string source = "ABCDABCEAAAABASABCDABCADABCDABCEAABCDABCEAAABASABCDABCAABLAKABCDABABCDABCEAAADSFDABCADABCDABCEAAABCDABCEAAABASABCDABCADABCDABCEAAABLAKABLAKK";
// string pattern = "abcaaabcab";
string pattern = "ABCDABCEAAABASABCDABCADABCDABCEAAABLAK";
int next[pattern.length()] = { NULL };
get_next(pattern, next);
cout << "next数组: \t";
for (int i = ; i < pattern.length(); i++)
cout << next[i] << " ";
cout << endl;
int pos = search(source, pattern, next);
if (- != pos) {
cout << "匹配成功,模式串在主串中首次出现的位置是: 第" << pos + << "位";
getchar();
return ;
} else {
cout << "匹配失败";
}
getchar();
return ;
}

执行结果:

next数组: -
匹配成功,模式串在主串中首次出现的位置是: 第97位

KMP算法优化

再回过头去看模式串2的next数组的图:

字符串匹配的 KMP算法

如果模式串和主串的匹配在j = 6(b)处失败的话,根据j = next[6] = 1得知下一次匹配从j = 1处开始,j = 1处的字符和j = 6处的字符同为c,因此这次匹配必定会失败。 
同样的,模式串和主串的匹配在j = 7(c)处或在j = 9(b)处失败的话,根据next数组偏移后下一次匹配也必定会失败。

考虑如果模式串是: aaaac,根据一般的KMP算法求出的next数组及匹配过程如下:

字符串匹配的 KMP算法

显而易见,在第二次匹配失败后,第三、四、五次匹配都是没有意义的,j = next[3]、j = next[2]、j = next[1]、j = next[0]这四处的字符都是a,在j = 3(a)处匹配失败时,根据模式串本身就应该可以得出结论:可以跳过j = 2(a)、j = 1(a)、j = 0(a)的匹配,直接从i = i + 1 、j = 0处开始匹配,所以优化过后的next数组应该是:

字符串匹配的 KMP算法

代码实现

优化后的求next数组的代码如下:

void get_next(string pattern, int next[]) {
// !!!!!!!!!!由网友(评论第一条)指出该算法存在问题,更新后的代码在上方,新算法的优化代码暂未实现,但是优化思路是正确的。 // int i = 0; // i用来记录当前计算的next数组元素的下标, 同时也作为模式串本身被匹配到的位置的下标
// int j = 0; // j == -1 代表从在i的位置模式串无法匹配成功,从下一个位置开始匹配
// next[0] = -1; // next[0]固定为-1
// int p_len = pattern.length();
// while (++i < p_len) {
// if (pattern[i] == pattern[j]) {
// // j是用来记录当前模式串匹配到的位置的下标, 这就意味着当j = l时,
// // 则在pattern[j]这个字符前面已经有l - 1个成功匹配,
// // 即子串前缀和后缀的最长公共匹配字符数有l - 1个。
// next[i] = j++;
//
// // 当根据next[i]偏移后的字符与偏移前的字符向同时
// // 那么这次的偏移是没有意义的,因为匹配必定会失败
// // 所以可以一直往前偏移,直到
// // 1): 偏移前的字符和偏移后的字符不相同。
// // 2): next[i] == -1
// while (next[i] != -1 && pattern[i] == pattern[next[i]]) {
// next[i] = next[next[i]];
// }
// } else {
// next[i] = j;
// j = 0;
// if (pattern[i] == pattern[j]) {
// j++;
// }
// }
// }
}
上一篇:CSS3背景相关新增属性


下一篇:多页的TIFF图片在aspx页面分页显示