KMP算法的核心,是一个被称为部分匹配表(Partial Match Table)的数组。对于字符串“abababca”,它的PMT如下表所示:
字符串的前缀和后缀定义:
如果字符串A和B,存在A=BS,其中S是任意的非空字符串,那就称B为A的前缀。例如,”Harry”的前缀包括{”H”, ”Ha”, ”Har”, ”Harr”},我们把所有前缀组成的集合,称为字符串的前缀集合。
同样可以定义后缀A=SB, 其中S是任意的非空字符串,那就称B为A的后缀,例如,”Potter”的后缀包括{”otter”, ”tter”, ”ter”, ”er”, ”r”},然后把所有后缀组成的集合,称为字符串的后缀集合。要注意的是,字符串本身并不是自己的后缀。
有了这个定义,就可以说明PMT中的值的意义了。PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。例如,对于”aba”,它的前缀集合为{”a”, ”ab”},后缀 集合为{”ba”, ”a”}。两个集合的交集为{”a”},那么长度最长的元素就是字符串”a”了,长 度为1,所以对于”aba”而言,它在PMT表中对应的值就是1。再比如,对于字符串”ababa”,它的前缀集合为{”a”, ”ab”, ”aba”, ”abab”},它的后缀集合为{”baba”, ”aba”, ”ba”, ”a”}, 两个集合的交集为{”a”, ”aba”},其中最长的元素为”aba”,长度为3。
保持i指针不动,然后将j指针指向模式字符串的PMT[j −1]位即可
有next[6]=pmt[5]=4; 同理可以发现规律: next[j]=ptm[j-1]的关系,因为j-1>=0,固有j>=1。又因为由前面知ptm[0]=0, 故next[1]=0。这样,还有next[0]未定义,为了编程方便,一般约定next[0]=-1。注意,next[0]纯粹凑数的,实际根本不会用到它。
public class KMP {
/**
* 求出一个字符数组的next数组
* @param t 字符数组
* @return next数组
*/
public static int[] getNextArray(char[] t) {
int[] next = new int[t.length];
next[0] = -1;
next[1] = 0;
int k;
for (int j = 2; j < t.length; j++) {
k=next[j-1];
while (k!=-1) {
if (t[j - 1] == t[k]) {
next[j] = k + 1;
break;
}
else {
k = next[k];
}
next[j] = 0; //当k==-1而跳出循环时,next[j] = 0,否则next[j]会在break之前被赋值
}
}
return next;
}
/**
* 对主串s和模式串t进行KMP模式匹配
* @param s 主串
* @param t 模式串
* @return 若匹配成功,返回t在s中的位置(第一个相同字符对应的位置),若匹配失败,返回-1
*/
public static int kmpMatch(String s, String t){
char[] s_arr = s.toCharArray();
char[] t_arr = t.toCharArray();
int[] next = getNextArray(t_arr);
int i = 0, j = 0;
while (i<s_arr.length && j<t_arr.length){
if(j == -1 || s_arr[i]==t_arr[j]){
i++;
j++;
}
else
j = next[j];
}
if(j == t_arr.length)
return i-j;
else
return -1;
}
public static void main(String[] args) {
System.out.println(kmpMatch("abcabaabaabcacb", "abaabcac"));
}
}