KMP—C语言实现-阿里云开发者社区

开发者社区> 人工智能> 正文

KMP—C语言实现

简介: KMP算法

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

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*。



版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章