Java实现KMP算法

转载请注明出处：http://blog.csdn.net/jevonscsdn/article/details/60874054 【Jevons’Blog】

本文知识来源于以下资料，欲想了解原理请熟读下面引用文章：

阮一峰：字符串匹配的KMP算法 JULY : 从头到尾彻底理解KMP

KMP算法简介

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。

KMP算法

next数组优化版Java实现

/** * <p>Title: KMPAlgorithm</p> * <p>Description: KMP算法java实现</p> * <p>Company: </p> * @author jevons * @date 2017年3月8日 下午3:43:00 */ public class KMPAlgorithm { public static void main(String[] args) { String source = "abchhabchabchabchcaaaabceabddh"; String target = "abceab"; System.out.println(KmpSearch(source, target)); } public static int KmpSearch(String source, String target) { // 转为字符型数组 char[] s = source.toCharArray(); char[] t = target.toCharArray(); // 获取next数组 int[] next = next(target); int i = 0;// 主串下标 int j = 0;// 模式串下标 while (i < s.length && j < t.length) { if (j == -1 || s[i] == t[j]) { i++; j++; } else { j = next[j]; } } if (j == t.length) { return i - t.length; } return -1; } //next数组优化版 public static int[] next(String target) { char[] t = target.toCharArray(); int[] next = new int[t.length]; next[0] = -1; int k = -1; int j = 0; while (j < next.length - 1) { if (k == -1 || t[j] == t[k]) { k++; j++; // =============== // 较优化前的next数组求法，改变在以下四行代码。 if (t[j] != t[k]) { next[j] = k;// 优化前只有这一行。 } else { // 优化后因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归。 next[j] = next[k]; } // =============== } else { k = next[k]; } } return next; } }

下面将其与String源码中indexOf函数性能对比：

/** * <p>Title: KMPAlgorithm</p> * <p>Description: KMP算法java实现</p> * <p>Company: </p> * @author jevons * @date 2017年3月8日 下午3:43:00 */ public class KMPAlgorithm { public static void main(String[] args) { String source = "abchhabchabchabchcaaaabceabddh"; String target = "abceab"; System.out.println("匹配成功，下标为："+indexOf(source, target)); System.out.println("匹配成功，下标为："+KmpSearch(source, target)); } public static int KmpSearch(String source, String target) { int count = 0; // 转为字符型数组 char[] s = source.toCharArray(); char[] t = target.toCharArray(); // 获取next数组 int[] next = next(target); int i = 0;// 主串下标 int j = 0;// 模式串下标 while (i < s.length && j < t.length) { //若j!=-1,则必然会发生字符比较 if(j!=-1){ count++; } //========= if (j == -1 || s[i] == t[j]) { i++; j++; } else { j = next[j]; } } System.out.println("KMP匹配法比较次数为：" + count); if (j == t.length) { return i - t.length; } return -1; } //next数组优化版 public static int[] next(String target) { char[] t = target.toCharArray(); int[] next = new int[t.length]; next[0] = -1; int k = -1; int j = 0; while (j < next.length - 1) { if (k == -1 || t[j] == t[k]) { k++; j++; // =============== // 较优化前的next数组求法，改变在以下四行代码。 if (t[j] != t[k]) { next[j] = k;// 优化前只有这一行。 } else { // 优化后因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归。 next[j] = next[k]; } // =============== } else { k = next[k]; } } return next; } //这里将String中的indexOf方法搬过来进行匹配次数比较 public static int indexOf(String source, String target) { // TODO Auto-generated method stub return indexOf(source.toCharArray(), 0, source.toCharArray().length, target.toCharArray(), 0, target.toCharArray().length, 0); } public static int indexOf(char[] source, int sourceOffset, int sourceCount, char[] target, int targetOffset, int targetCount, int fromIndex) { int count = 0; if (fromIndex >= sourceCount) { return (targetCount == 0 ? sourceCount : -1); } if (fromIndex < 0) { fromIndex = 0; } if (targetCount == 0) { return fromIndex; } char first = target[targetOffset]; int max = sourceOffset + (sourceCount - targetCount); for (int i = sourceOffset + fromIndex; i <= max; i++) { /* Look for first character. */ count++; if (source[i] != first) { while (++i <= max && source[i] != first) { count++; } ; } /* Found first character, now look at the rest of v2 */ if (i <= max) { int j = i + 1; int end = j + targetCount - 1; //为方便统计次数，对String源码稍作调整 for (int k = targetOffset + 1; j < end; ) { count++; if(source[j] == target[k]){ j++; k++; }else{ break; } }; //================= if (j == end) { System.out.println("暴力匹配法比较次数为：" + count); /* Found whole string. */ return i - sourceOffset; } } } System.out.println("暴力匹配法比较次数为：" + count); return -1; } }

输出结果：

暴力匹配法比较次数为：38 匹配成功，下标为：21 KMP匹配法比较次数为：34 匹配成功，下标为：21

从结果可以看出，在较长的主串下，KMP算法的性能比暴力匹配法高，并且主串越长，匹配性能差距越大。或许有人会说，next数组的比较还没算进去呢。但是你要这么想，如果相对于远长于模式串的主串来说，那next那点比较量真的算是微不足道了。