[牛客算法系列] KMP算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[牛客算法系列] KMP算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1679字，纯文字阅读大概需要3分钟。

内容图文

题目

• 给定两个字符串source 和 match， 长度分别为 N 和 M。实现一个算法，如果字符串source 中，含有子串match, 则返回match 在 source 中的开始为位置，不含有返回-1.
• 举例
  source = “acbc”, match = “bc” , 返回2.
  source = “acbc”, match = “bcc” , 返回-1；
• 要求，如果match 的长度大于source 的长度（M > N）source 必然不会含有match， 可直接返回-1。但如果N >= M ,要求时间复杂度为O(N).

分析代码

• 最普通的解法是从左到右遍历source 的每个字符，然后看如果以当前字符作为第一个字符出发是否匹配出match。时间复杂度较高O(N * M)。
• 本文KMP解法能够做到时间复杂度O(N)
• 主要是生成match字符串的nextArr 数组，这个数组的长度与match字符串的长度一样，nextArr[i]的含义是在match[i]之前的字符串match[0…i-1] 中，必须以match[i-1]结尾的后缀子串（不能含有match[0]）与必须以match[0]开头的前缀子串（不能含有match[i - 1]）最大的匹配长度是多少。这个长度是nextArr[i]的值。

代码

// kmp

public int[] getNextArray(char[] ms){
	if(ms.length == 1){
		return new int[]{-1};
	}
	int[] next = new int[ms.length];
	next[0] = -1;
	next[1] = 0;
	int pos = 2;
	int cn = 0;
	while(pos < next.length){
		if(ms[pos - 1] == ms[cn]){
			next[pos++] == ++cn;
		}else if(cn > 0){
			cn = next[cn];
		}else{
			next[pos++] = 0;
		}
	}
	return next;
}

pubulic int kmp(String source, String match){
	int i = 0, j = 0;
	char[] src = source.toCharArray();
	char[] mat = match.toCharArray();
	int sLen = src.length;
	int mLen = mat.length;
	int[] next = getNextArray(mat);
	while(i < sLen && j < mLen){
	//如果j = -1 ,或者当前字符匹配成功（src[i] = mat[j]), 都让i++，j++
		if(j == -1 || src[i] == mat[j]){
			i++;
			j++;
		}else{
			//如果j!= -1 且当前字符匹配失败，则令i 不变， j = next[j] ，即让match 串 右移 j- next[j] 个单位
			j = next[j]; //此处体现next 数组的作用， source 数组无需退回。
		}
	}
	if(j == mLen)
		return i - j;
	return -1;
}

内容总结

以上是互联网集市为您收集整理的[牛客算法系列] KMP算法全部内容，希望文章能够帮你解决[牛客算法系列] KMP算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---