C语言实现KMP算法和个人理解

Last updated on a year ago

以下内容皆为个人理解，可能存在不足或错误，请注意辨识。同时KMP不止一种实现方法

什么是KMP算法

KMP模式匹配算法是一种用来查找字符串的算法，由K,M,P（首字母）三位大佬提出，是一种朴素模式匹配算法更高效的方法。能有效缩短时间。

KMP算法与朴素算法比较

朴素算法，是一种很直观的算法，我们定义一个i和j，两个字符串s和t，s为主串，t为要查找的子串，i是指向s某个位置的指针，j同理指向t。

1
2
3
4
char s[MAXSIZE];
char t[MAXSIZE];
int i = 0;
int j = 0;

接着将子串与主串的各自元素进行比较，若相同则i,j指针后移继续比较，直到j遍历完子串，说明完全相等，返回i-j，就是子串在主串的位置。而若是在中途出现不匹配的，则将j指向重新指向头部，i移动到i-j+1的位置，重新遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
while ( i < strlen(s) && j < strlen(t))
{
	if( s[i] == t[j])
    {
		i++;
        j++;
    }
    else
    {
		i = i - j + 1;
    }
}
if (j == strlen(t))
    return i-j;
else
    return 	-1;	//t不在s内

也就是说，朴素算法出现某个元素对不上时，需要将指针回滚，这样原本遍历过的元素又要重新遍历一次，而KMP算法就是一种只向前的算法，将遍历过的元素利用起来。

举个例子

1
2
s = "ababbaa;
t = "ababc";

当我们比较到第5个元素时，发现s[4]与t[4]对不上，如果是朴素算法，我们接下来就是从s[1]与t[0]开始重新比较，但是我们可以看到

c的前面元素是abab，前两个和后两个是一样的，同时主串也是abab，也就是说，我们可以跳过子串的前2个元素，因为它们和主串的3，4元素是一样的，所以不必比较。也就是直接比较s[4]与s[2]。
像这种ab ab称为公共前后缀，比如ab efg ab，它们的最长公共前后缀就是ab，有多长，我们就可以跳过多少个元素。那么我们要怎么得出这个最长公共前后缀呢？

我们可以建立一个next数组，将每个部分的最长公共前后缀记录。如：

1
t = "ababaa"

对应的next数组为

1
next = {0 0 1 2 3 1}

解释一下：a 只有一个 最长公共为0，ab没有公共 为0， aba最长公共为1， abab最长公共为2, ababa最长公共为3（aba）, ababaa最长公共为1（a）。

就是从第一个元素开始不断往后扩展，每扩展一次判定一次最长公共前后缀。next就是用于记录每次扩展后的最长公共前后缀。那么next如何利用到KMP算法呢？

KMP算法C语言实现

我们前面说了，在对比s和t中的元素时，若出现不等于的情况，可以直接跳过最长公共前后缀个元素，接着比较。s=“ababbaa” t=“ababc”。我们对比到第5个元素时，发现不相同，我们就看next数组的第4（就是5-1）个元素，它的值是2，说明前面这些元素最长公共前后缀是2，也就是说，我们可以跳过t的前2个元素，直接从t的第3个元素对比。具体代码实现为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int indexKMP(string s, string t){
	int i = 0;	//主串s的元素
	int j = 0;	//子串t的元素
	int next[100];
	getNext(t, next);
	while( i < strlen(s) && j < strlen(t)){		//当未达到主串或子串的末尾时，继续
		if( s[i] == t[j]){		//元素相等，主串指针和子串指针同时后移
			i++;
			j++;
		}
		else {
			if(j == 0){			//如果j等于0，则子串无法再回溯，说明主串的对应元素不是遍历过的子串中的一部分，下一个
				i++;			//主串指针后移
			}
			else{				//如果不相等且j != 0 ，则需要对子串指针进行回溯
				j = next[j-1];	//回溯并跳过公共前后缀
			}
		}
	}
	if( j == strlen(t))			//子串被遍历完，说明子串存在于主串
		return i - j;
	else 
		return -1;
}

创建next数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void getNext(string t, int* next){
	int f = 0;	//前缀末尾元素 和 最长公共前后缀长度
	int b = 1;	//后缀末尾元素
	next[0] = 0;
	while( b < strlen(t)){
		if(t[f] == t[b]){	//相等
			f++;			//前缀指针后移，同时也表示最长公共前后缀长度+1
			next[b] = f;	//记录b位置的最长公共前后缀长度
			b++;			//后缀指针后移
		}
		else{				//不相等
			if( f == 0){	//如果前缀指针指向0/当前最长公共前后缀长度为0 且t[f] != t[b]
				next[b] = 0;	//b位置的最长公共前后缀长度为0
				b++;			//后缀指针后移
			}
			else{			//如果f不为0且前后缀不等
				f = next[f-1];	//前缀指针回溯，并跳过公共部分
			}
		}
	}
}