KMP算法

引用百度百科的介绍

 思路：

由于直接两层循环求子串匹配主串的位置或次数效率特别低，所以我们需要改进算法，如此KMP算法。改进的关键就是当子串与主串不匹配时，可以使主串上的“指针”（代码中是 j ）往回回溯距离最小。

那么对于nex数组，是记录子串不匹配时需要回溯的位置。同样需要 i ，j 两个“指针”，i 是当前匹配的位置（依次递增至子串遍历结束），j 是记录匹配回溯的位置。j 和 nex[0] 初始值都设置为 - 1，然后遍历。首先判断 j 的值是不是 - 1，如果是 - 1 的话当做匹配的情况（代表重新开始匹配）；如果不是 - 1 并且 此时 i , j 所对应的值不相等，代表不匹配的情况。

当匹配时，i , j 的值都加 1 （为了接着匹配更多的字符），然后把当前位置的 nex 数组进行更新。

当不匹配时，j 回溯到当前对应的 nex 数组值。

对于KMP里的子串匹配主串方法，i ，j 分别代表 主串 和 子串 下标（初始都为0，子串主串的下标从0开始），在遍历主串的过程中，当 j 等于 -  1 时，归入匹配的情况（说明匹配主串过程中发生了回溯，且回到了子串第一个位置，即下标为0）。当 j ！= -1 并且 i , j 所对应的主串、子串值不一样时，明显为不匹配情况。其他情况都是匹配的情况。

当匹配时， i，j 的值都加 1 接着遍历主串。

当不匹配时，j 回溯到当前 j 该回溯的位置。

当 j 的值等于子串长度时（实际应该是子串长度减 1 ，由于每次成功 j 自增所以为 其长度），说明此时完全与子串匹配，进行相关的记录数据等。

import java.util.Scanner;

public class KMP {

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		
		String s = cin.next();//主串
		String t = cin.next();//匹配串
		
		// abcabcabca abc 
		// aaa aa
		KMP(s, t);
	}

	static int N = 100;
	static int[] nex = new int[N];
	private static void KMP(String s, String t) {
		getNex(t);
		int n = s.length();
		int m = t.length();
		int i = 0;
		int j = 0;
		
		int cnt = 0;// 计算匹配的次数
		
		while(i < n) {
			while(j != -1 && s.charAt(i) != t.charAt(j)) {
				j = nex[j];
			}
			i++;
			j++;
			if(j == m) {// 匹配成功时
				cnt ++;
				
				j = nex[j];// 重叠匹配时的回溯
//				j = 0;// 非重复匹配的回溯
//				System.out.println(i - m);// 依次返回匹配的下标位置
			}
		}
		System.out.println("出现了" + cnt + "次");
	}

	private static void getNex(String t) {
		int len = t.length();
		int i = 0;// t下标
		int j = -1;// 回溯的位置
		nex[0] = -1;// j初始位置
		while(i < len) {
			while(j != -1 && t.charAt(i) != t.charAt(j)) {//不匹配时
				j = nex[j];//最少回溯到的位置
			}
			nex[++i] = ++j;//更新nex数组（更新当前i所对应的回溯位置）
		}
	}
}

---

对于以上代码，cnt 值计算的是匹配成功的次数。

j = nex[j]; 开启时表示重叠匹配的次数； j = 0; 开启时表示不重叠匹配的次数。

匹配成功后输出的 i - m 的值表示每次匹配成功后对于此时主串的下标。

该算法由我同学帮助我理解完成的，总结不够详细（很多博客有详细的推导 nex 数组过程，大家可以看看），再次感谢帮助我的人！！！

---

如有错误或不合理的地方，敬请指正哦~

加油！！