KMP算法随感_求理解是否正确

今天看的   [转自 matrix67.com]KMP算法详解  。然后根据自己的理解写了个java的程序，也不知道自己理解KMP字符串比较算法是否正确，希望大家能多提意见。

 

 

package com.dianziermu.arith;

/**
 * 字符串比较之KMP算法
 * 
 * @think 思路： <br>
 *        如果mainChar[i]==subChar[0]，则继续比较mainChar[i+1]和subChar[1]是否相等。 <br>
 *        一直相等则一直比较到subChar[subChar.length-1]与主串的是否相等。如果相等则返回i，找到结果结束。 <br>
 *        如果有不等的，则比较mainChar[i+1]与subChar[0]是否相等，一直比较下去。 <br>
 *        直到循环到mainChar[i+j]时，若i+j+subChar.length>mainChar.length,<br>
 *        说明剩余的主串上的字符串不够子串的长度，肯定不会匹配，退出。
 * @author 点子二木
 * @date 2009-5-4
 * @version 1.0
 */
public class KMPMine {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String mainStr = "ababaab";
		String subStr = "aab";
		System.out.println("首索引为：" + KMP(mainStr, subStr));
	}

	/**
	 * 比较主串中是否有子串
	 * 
	 * @param mainStr主串
	 * @param subStr子串
	 * @return 有-返回子串在主串中首字母的索引，主串起始索引为0； 无-返回（-1）
	 */
	private static int KMP(String mainStr, String subStr) {
		int comfortIndex = -1;
		char[] mainChar = mainStr.toCharArray();
		char[] subChar = subStr.toCharArray();

		int mainCurrentIndex = 0;// 主串当前索引
		int mainEqualIndex = 0;// 正在比较的已经相等的主串起始位置
		int subCurrentIndex = 0;// 子串当前索引
		int subEqualIndex = 0;// 子串中已经有匹配的个数

		while (mainCurrentIndex < mainChar.length) {

			// System.out.println("循环"+mainCurrentIndex);
			// 循环到剩余的主串上的字符串不够子串的长度，肯定不会匹配，退出
			if (mainEqualIndex + subChar.length > mainChar.length) {
				return comfortIndex;
			}

			if (mainChar[mainCurrentIndex] == subChar[subCurrentIndex]) {// 匹配
				// 比较到子串最后一位也匹配
				if (subEqualIndex == subChar.length - 1) {// 整个都匹配
					comfortIndex = mainEqualIndex;
					return comfortIndex;
				}

				// 移动子串的索引
				subCurrentIndex++;
				mainCurrentIndex++;
				subEqualIndex++;
			} else {
				// 移动整个子串，将当前索引移动到本次整个串比较的的最前端（即mainEqual）的下一位
				mainEqualIndex++;
				mainCurrentIndex = mainEqualIndex;
				subCurrentIndex = 0;
				subEqualIndex = 0;
			}
		}

		return comfortIndex;
	}

}

 

 

 

 运行结果为：

                   首索引为：4    

 

 

 

评论

2 楼 dianziermu 2009-05-12  

kdboy 写道

错误的，你还没理解kmp算法。1、主串索引不回溯2、字串索引根据自匹配算法确定回溯位置

我修改了一下，现在对么，子串如何回溯？？？？

package com.dianzi.arith;

/**
 * 字符串比较之KMP算法<br>
 * 即：比较主串中是否包含子串，如果包含,则返回在主串的索引位置（主串首索引为0）<br>
 * 						  如果不包含，则返回-1；<br>
 * 
 * @think 思路： <br>
 *        按顺序循环主串索引，循环到剩余的主串上的字符串不够子串的长度，肯定不会匹配，退出。<br>
 *        在每一个主串索引上，比较此时 “以主串索引位置为开始、子串长度的字符串和子串是否相等”<br>
 *        若相等则找到，返回主串索引位置即可；若不等则未找到，继续循环主串索引<br>
 * @author 点子二木
 * @date 2009-5-12
 * @version 1.0
 */
public class KMPMine {

	public static void main(String[] args) {
		String mainStr = "ababaab";
		String subStr = "aab";
		System.out.println("首索引为：" + KMP(mainStr, subStr));
	}

	/**
	 * 比较主串中是否有子串
	 * 
	 * @param mainStr主串
	 * @param subStr子串
	 * @return 有-返回子串在主串中首字母的索引，主串起始索引为0； 无-返回（-1）
	 */
	public static int KMP(String mainStr, String subStr) {
		int comfortIndex = -1;
		if (mainStr == null) {
			mainStr = "";
		}
		if (subStr == null) {
			subStr = "";
		}
		char[] mainChar = mainStr.toCharArray();
		char[] subChar = subStr.toCharArray();

		// 循环到剩余的主串上的字符串不够子串的长度，肯定不会匹配，退出
		for (int mainIndex = 0; mainIndex <= mainChar.length - subChar.length; mainIndex++) {
			String mainSubStr = mainStr.substring(mainIndex, mainIndex
					+ subChar.length);// 被截的主串
			if (compareSubStr(mainSubStr, subStr)) {// 相等
				return mainIndex;
			}
		}
		return comfortIndex;
	}

	/**
	 * 比较子串和子串长度相等的被截的主串是否相等
	 * 
	 * @param mainSubStr被截主串
	 * @param subStr子串
	 * @return 返回：true-相等；false-不相等
	 */
	private static boolean compareSubStr(String mainSubStr, String subStr) {
		char[] mainSubChar = mainSubStr.toCharArray();
		char[] subChar = subStr.toCharArray();

		for (int subIndex = 0; subIndex < subChar.length; subIndex++) {
			if (mainSubChar[subIndex] == subChar[subIndex]) {// 匹配
				// System.out.println("循环" + subIndex);//测试循环次数
				// 比较到子串最后一位也匹配
				if (subIndex == subChar.length - 1) {// 整个都匹配
					return true;
				}
			} else {// 不匹配，移动主索引
				return false;
			}
		}
		return false;

	}
}

1 楼 kdboy 2009-05-05  

错误的，你还没理解kmp算法。
1、主串索引不回溯
2、字串索引根据自匹配算法确定回溯位置