Knuth-Morris-Pratt 算法,又称KMP算法
主要思想:当patter在某一位置与string匹配失败时,我们除了知道从string的这个位置进行匹配失败这个结果外,是否可以从前面的匹配中获得更多的信息呢。至少还有一个信息,匹配失败前面的字符串,我们已经知道。例如:
abcabcabcdef --------- string
abcabcdef --------- pattern
当匹配到第7个字符时,虽然匹配失败了,但是除了这个结果,我们还可以知道string前面的字符串是已经匹配成功了的字符串,即abcabc。而patter本身是abcabcdef,那么就可以知道至少需要向右滑动3个字符,才可能匹配:
abcabcabcdef
abcabcdef
KMP就是利用已经匹配了的字符串这个信息,来进行尽可能的向右滑动,避免无谓的比较。
那么究竟当不匹配的时候,可以向右滑动多远呢?
以上面的pattern "abcabcdef"为例:
当第一个字符不匹配的时候,没有额外信息,那么就向右滑动1个字符。
当第二个字符不匹配的时候,说明之前匹配的字符为a,但是我们是第二个字符不匹配,还是只能向右滑动1个字符。
当第三个字符不匹配的时候,说明之前匹配的字符为ab,那么可以向右滑动2位;
当第四个字符不匹配的时候,说明之前匹配的字符为abc,那么可以向右滑动3位;
当第五个字符不匹配的时候,说明之前匹配的字符为abca,那么也只能向右滑动3位;
........................
那么KMP算法的关键问题就是计算pattern某位置匹配失败的时候,可以向右滑动的位数。
下面白话一下如何计算这个滑动位数,0匹配和1匹配时,向右滑动都为1。那么当在第n(n>=2)不匹配时,那么我们可以从偏移1位到m位进行尝
试,m最大为n-1。只要0 != strncmp(pattern, pattern+m, n-m-1),那么就可以继续增加m值。
大致的代码如下:
static void cal_next_table(const char *pattern, int len, int *table)
{
int i,j;
/* table[0] 为哨兵 */
table[0] = 1;
for (i = 1; i <= len; ++i) {
table[i] = table[i-1];
for (j = table[i]; j < i; ++j) {
if (0 != strncmp(pattern, pattern+j, i-j-1)) {
table[i]++;
}
else {
break;
}
}
}
}
通过上面的函数,将生成右移的table表。当第n个不匹配时,可以向右滑动table[n]个字符。
下面是测试代码:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
static void cal_next_table(const char *pattern, int len, int *table)
{
int i,j;
table[0] = 1;
for (i = 1; i <= len; ++i) {
table[i] = table[i-1];
for (j = table[i]; j < i; ++j) {
if (0 != strncmp(pattern, pattern+j, i-j-1)) {
table[i]++;
}
else {
break;
}
}
}
}
int main()
{
char pattern[] = "abcabcdef";
int table[sizeof(pattern)+1] = {};
cal_next_table(pattern, sizeof(pattern), table);
int i;
printf("%s\n", pattern);
for (i = 1; i < sizeof(pattern); ++i) {
printf("%d", table[i]);
}
printf("\n");
return 0;
}
结果如下:
abcabcdef
112333378
最后总结一下,我们从KMP算法中可以获得什么?除了知道这个字符串匹配算法,我们还要争取 获得更多的东西,比如即尽可能的从已经处理过得操作或数据中获得更多的信息。