KMP算法

如果要解决问题：有两个字符串 str1，str2，求 str1 是否包含 str2 ，如果包含，求位置

------ 一般方法 -------
每次从 str2 的 0 位置开始，依次和 str1 匹配
例如 aaab 匹配 ab
先 从 ab 的 a 开始匹配，可以匹配到 aaab 的 a，但是匹配不到 aaab 的 b
从 ab 的 a 开始匹配，匹配 aaab 的第二个 a 开始匹配，这次匹配还不行
第三次 可以匹配到
如果 str1 的长度为 N，str2 的长度为 M，则时间复杂度为 O(N*M)

---

KMP 算法：让前面匹配过的信息指导后面的匹配
例如字符串 abcabcd
先拿 一个字符，从前往后拿是 a，从后往前拿是 c，a≠c，不匹配
拿 两个字符，从前往后是 ab，从后往前是 bc，ab≠bc，不匹配
拿 三个字符，从前往后是 abc，从后往前是 abc，abc=abc，匹配，d=3
拿 四个字符，得到 abca 和 cabc，不匹配
拿 五个字符，得到 abcab 和 bcabc，不匹配
不能继续再拿，因为拿的字符数量不能超过原本数量，因此 最长匹配度 为 d=3，d 暂存数据 d=3 ，也即 d 的最长前缀和最长后缀匹配度为 d=3
例如字符串 aaaaab
一直拿，可拿 4个字符还是匹配的，所以 暂存数据 b=4，也就是说 b的最长前缀和最长后缀匹配度为 4

KMP 算法
先求 str2 的最长前缀和最长后缀匹配度的信息
例如字符串 ababac
先建立int[]
int[0] = -1 (开始的字符规定是-1)
int[1] = 0 (第二个字符规定是0)
int[2] = 第一个和第二个字符相等吗?1:0
int[……] = 按照方法快速填充数组
最终的 int[] = {-1 0 0 1 2 3}

假设

假设， str2 从 0 位置开始，一直可以匹配 str1（从i位置开始匹配），但是，突然在 Y 位置 和 X 位置不匹配了
我们又知道， str2 字符串的 最长前缀和最长后缀的匹配信息，如上图的两个椭圆

流程
将 str2 的头，和 j 位置对其，再从 X 和 Z 位置开始匹配即可
可以看到，X Y Z 前面的那一串字符串片段是一样的，因此，无需让 str2 和 str1 的那段再次匹配

KMP 认为，从 i 位置 到 j 位置，一律不能配出 str2，这就加速了匹配过程
如果能匹配处 str2 会与 str2 的最长前缀和最长后缀发生矛盾

例子： str1 = abkababkabD str2 = abkababkabF

next[] 的求法
next[0] next[1] next[2] 可以直接赋值
next[i] 的求法 利用归纳法
如果 next[i-1] 已知，且 next[i-1] = a, 那么只需要看 str2[a] 是否等于 str2[i] 即可
如果相等，那么 next[i] = a+1
如果不等，那么 有下面的步骤

package kmp;

public class KMP {

public static int getIndexOf(String s, String m) {
	
	if(s == null || m == null || m.length()<1 || s.length()<m.length()) {
		return -1;
	}
	
	char[] str1 = s.toCharArray();
	char[] str2 = m.toCharArray();
	int[] next = getNextArray(str2);
	int i1 = 0;
	int i2 = 0;
	
	while(i1<str1.length && i2<str2.length) {
		if(str1[i1] == str2[i2]) {
			i1++;
			i2++;
		} else {
			//如果当前字符不匹配，且 str2 已经来到了 第 0 个字符的
			//i1指针 ++
			if(next[i2] == -1) {
				i1++;
			} else {
				//当前字符不匹配，且 str2 没有来到 第 0 个字符
				//i2 往右推进
				i2 = next[i2];
			}
			
		}
	}
	//如果 str2 已经划过了所有字符  那么肯定包含此字符串
	return i2 == str2.length? i1-i2:-1;
}

private static int[] getNextArray(char[] str2) {
	if(str2 == null || str2.length<1) return null;
	if(str2.length == 1) return new int[]{-1};
	int[] next = new int[str2.length];
	next[0] = -1;
	next[1] = 0;
	int i = 2;
	int cn = 0;
	while(i<next.length) {
		if(str2[i-1] == str2[cn]) {
			//匹配的话  看 cn 位置的字符是否等于待比较的字符
			next[i] = cn + 1;
			i = i + 1;
			cn = cn + 1;
		} else if(cn > 0){
			//不匹配 往前跳
			cn = next[cn];
		} else {
			//无法继续跳   那么最长前缀和最长后缀匹配 长度为 0
			next[i] = 0;
			i = i + 1; 
		}
	}
	return next;
}

}

例题1：判断一棵树是否为另一棵树的子树
将树序列化，如果是存在的节点，用 1 标记，如果是空节点，用 # 占位符标记

可以以先序遍历的方式序列化为 1_1_1_##1##1_1###_
可以用 序列化字符串 反序列化重新建树

将两棵树序列化，如果 str2 是 str1 的字串，那么 树2 必是 树1 的子树
因为 是有 # 占住位了