package net.yk.string;
public class KMP {
public static void main(String[] args) {
String major = "abababcabcabcda";
String mode = "abcd";
int[] next = new KMP().next(mode);
System.out.println(new KMP().index_KMP(major, mode, 1, next));
}
/**
* 获取字符串的部分匹配值
* @param str
* @return
*/
int[] next(String str) {
// 获取模式串的长度
int len = str.length();
// 创建字符数组用来存储模式串
char[] mode = new char[len + 1];
int[] next = new int[len + 1];
// 将模式串拷贝到字符数组中，从下标1开始
str.getChars(0, len, mode, 1);
int i = 1, j = 0;
next[1] = 0;
while (i < len) {
if (j == 0 || mode[i] == mode[j]) {
i++;
j++;
next[i] = j;
} else
j = next[j];
}
return next;
}
/**
* KMP 算法
*
* @param major
* @param mode
* @param pos
* @param next
* @return
*/
int index_KMP(String major, String mode, int pos, int[] next) {
int majorL = major.length();
int modeL = mode.length();
//从下标1开始存储数据
char majorChar[] = new char[majorL + 1];
char modeChar[] = new char[modeL + 1];
major.getChars(0, majorL, majorChar, 1);
mode.getChars(0, modeL, modeChar, 1);
int i = pos, j = 1;
while (i <= majorL && j <= modeL) {
if (j == 0 || majorChar[i] == modeChar[j]) {
++i;
++j;
} else
j = next[j];
}
if (j > modeL) {
return i - modeL;
} else
return 0;
}
}
java实现KMP算法
原文：http://blog.51cto.com/6631065/2046605
