转载请注明出处：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那点比较量真的算是微不足道了。