KMP算法

算法思想：

一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此称之为KMP算法。此算法可以在O (n+m)的时间数量级上完成串的模式匹配操作，其基本思想是：每当匹配过程中出现字符串比较不等时，不需回溯指针，而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离，继续进行比较。


package com.java.caul;

public class test2 {
private static int[] get_nextval(String t) {

int i = 0, j = -1;
int[] next = new int[t.length()];
next[0] = -1;
char[] s = t.toCharArray();

while (i < next.length-1) {
if (j == -1 || s[i] == s[j]) {
i++;
j++;
next[i] = j;
} else
j = next[j];

}
for (int k = 0; k < next.length; k++) {
System.out.print(next[k] + "  ");
}
System.out.println();
return next;
}

private static int index_KMP(String s, String t) {
int []next=get_nextval(t);
int i = 0;
int j = -1;
while (i < s.length() && j < t.length()) {
if (j == -1 || (s.charAt(i) == t.charAt(j))) {
i++;
j++;
} else
//j = (next[j] - 1);
j=next[j];
}
if (j >= t.length() - 1) {
return (i - t.length() + 1);
} else
return -1;
}

public static void main(String[] args) {
System.out.println(index_KMP("Test ititi ititit! Test ititit!这个会匹配2次", "ititit"));
System.out.println(index_KMP("abababababcababb","ababcabab")) ;

}

}


运行结果：

-1  0  0  1  2  3 
12
-1  0  0  1  2  0  1  2  3 
7

评论

1 楼 mars914 2012-02-11  

函数get_nextval是个死循环，怎么能得出结果？