KMP算法的原理和实现( 二 ) _KMP算法

文章插图

那么应该移动多少位呢？没错，就是5位。然后接着去匹配。

文章插图

至此，关于KMP的大体思路已经讲解完毕，接下来的关键就是如何求出一个字符串中对于所有位置的前缀与后缀最大匹配长度。也就是我们常说的next数组。
如何求next数组我们人为规定了next[0]=-1和next[1]=0，即0位置的前缀与后缀最大匹配长度是-1，而1位置的前缀与后缀最大匹配长度是0.现在我们假设要求i位置的前缀与后缀最大匹配长度，而现在又知道i-1位置的前缀与后缀最大匹配长度为7，那么，如果j位置的字符和i-1位置的字符相等的话，就可以得到i位置的前缀与后缀最大匹配长度为7+1=8.

文章插图

如果i-1位置的字符和j位置的字符不相等的话，而我们又知道j位置的前缀与后缀最大匹配长度为3，那么我们就去看看k位置的字符是否和i-1位置的字符相等，如果相等，则i位置的前缀与后缀最大匹配长度为3+1=4 。如果不等，则再继续以上操作，直到跳到0位置处，如果此时0位置还依然和i-1不等的话，那么i位置的前缀与后缀最大匹配长度为0 。

文章插图

以上这一段看着可能有点复杂，但是实际上很好理解，大家用纸和笔来画一下就清楚了！
下面是求next数组的代码

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 i1 = 0;int i2 = 0;int[] next = getNextArray(str2); // O (M)// O(N)while (i1 < str1.length && i2 < str2.length) {if (str1[i1] == str2[i2]) {i1++;i2++;} else if (next[i2] == -1) { // str2中比对的位置已经无法往前跳了i1++;} else {i2 = next[i2];}}// i1 越界或者i2越界了return i2 == str2.length ? i1 - i2 : -1;	}

利用next数组进行字符串匹配行为
按照以上的思路，我们就可以利用next数组去执行KMP算法了，最终我们是要得到str2在str1全匹配的str1的下标位置，以下图为例，最终KMP算法是要返回8，因为str2是在str1的下标为8的位置处匹配上的，如果str2没有被包含在str1中，那么返回-1.

文章插图

下面是利用next数组进行KMP算法的代码

public static 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 i = 2; // next数组的位置int cn = 0;while (i < next.length) {if (ms[i - 1] == ms[cn]) {next[i++] = ++cn;} else if (cn > 0) { // 当前跳到cn位置的字符，和i-1位置的字符配不上cn = next[cn];} else {next[i++] = 0;}}return next;	}