用JAVA语言实现的KMP算法.doc

package com.java.kmp;

/**
* KMP实现类
*
*/

public class KMP {

private long time1,time2;
private long count;

private int[] getNext(char[] B) {

int i, j;
int len = B.length;
int[] next = new int[len];
next[0] = 0;

for (j = 1; j < len; j++) {

i = next[j - 1];

while ((i > 0) && (B[i - 1] != B[j - 1])) {

i = next[i - 1];
}

next[j] = i + 1;
}
return next;
}

public void kmp(String msg) {

String string1 = "";
String pattern = "123456";
String test = "123";

int plen = pattern.length();
int tlen = test.length();
char[] p = pattern.toCharArray();
char[] t = test.toCharArray();
//char[] t = { 'a', 'b', 'a', 'a', 'b', 'c', 'a', 'c'};
int[] n = getNext(t);
for(int k = 0 ;k < n.length; k++){
System.out.println(n[k]);
}
if (plen < tlen) {

System.out.println("匹配失败");
}

int i = 1, j = 1, sum = 0;

//time1 = time.date();
time1 = System.nanoTime();

while(i <= plen && j <= tlen) {

if( j == 0 || p[i - 1] == t[j - 1]) {

if(j != 0){
sum++;
}
i ++;
j ++;

} else {

sum++;
j = n[j - 1];
}

if(j > tlen ){

break;
}
}

if( j > tlen ) {

string1 = string1 + "在主串中第" + (i - j + 1) + "位匹配成功 ;";
System.out.println("在主串中第"
+ (i - j + 1) + "位匹配成功 .");
}
else {

string1 = string1 + "匹配失败 ;";
System.out.println("匹配失败 .");
}

//time2 = time.date();
time2 = System.nanoTime();

/*
* for (int i = 0; i < size2; i++) { System.out.print(" " + P[i]); }
*/

System.out.println("KMP算法共匹配了 " + sum + " 次 .");
System.out.println("KMP算法开始时间为" + time1 + ".");
System.out.println("KMP算法结束时间为" + time2 + ".");
count = time2 - time1;
//string1 = string1 + "\n所用时间为：" + count + "ms.\n";
System.out.println("整个KMP算法共用时" + count + "ns.\n");

}

public static void main(String[] args) {

KMP kmp = new KMP();
kmp.kmp(); }

}