KMP—C语言实现

这是我的第一篇博客，希望以后可以坚持下去！

KMP原理：

     KMP是在字符串中寻找特定子串的算法。假设：给定字符串：S = "abcdefabcdex" ，下标用i表示；子串：T = "abcdex"，下标用j表示；

     我们希望在S中找到字串T，正常的方法是从S的第一个字符'a'与T的第一个字符'a'进行比较，然后依次比下去...当S找到"abcde"时，T也找到"abcde"，哈哈还有一 个就成功了，但是我们的运气不太好，S的下一个字符是'f'而T的下一个字符是'x'，这个时候按照一般的算法会回溯S的下标i到字符‘b'，然后重复上面的步骤，这里就有一个问题，当我们比较S的"abcde"和T的"abcde"的时候可以得到一个信息，那就是S的第一个字符’a' 后面的四个字符（即'b''c''d''e'）并没有与T的一个字符相同的字符,一般的算法并没有用到这个信息，而KMP就利用这个信息从而不必回溯S的下标i，只要回溯T的下标j（这里注意因为字串T中也会有重复的字符，所以j并不需要每次都回溯到第一个字符），KMP实现的关键就是j的回溯规则。通过分析j的回溯只跟字符串T有关，通过T建立j的回溯规则数组next,next[j]的值就是位置j要回溯的位置。

C语言实现代码：

// 建立next数组
int mknext(char const*T, int *next) {
	int len = strlen(T);
	int i = 0;
	int j = -1;
	next[0] = -1;
	while (i < len) {
		if (j == -1 || T[i] == T[j]) {
			i++;
			j++;
			next[i] = j;
		}
		else
			j = next[j];
	}
	return 0;
}

//KMP实现
int index_KMP(char const*S, char const*T, int pos) {
	int i = pos-1;
	int j = -1;
	int next[LIM];
	mknext(T, next);
	int S_len, T_len;
	S_len = strlen(S);
	T_len = strlen(T);
	while (i < S_len && j < T_len) {
		if (S[i] == T[j] || j == -1) {
			i++;
			j++;
		}
		else
			j = next[j];
	}
	if (j >= T_len)
		return i - T_len;
	else
		return -1;
}

这里有一个小问题：字符串数组作为函数形参声明的时候要用char const*,不能是const char*。