10/01/2010

KMP算法

以前学习数据结构的时候,有关KMP算法一直不是很懂。
今天详细的看了一下,找了一些相关的资料,自己用java写了个代码实现。
具体的原理就不累述了,资料在这里:
一些英文介绍:
中文java实现:

我自己写的代码:
package temp;

public class KMP {

private String text, pattern;
private int[] next;

public KMP(String text, String pattern) { 
this.text = text;
this.pattern = pattern;
this.next = new int[pattern.length()];
this.createNext();
}

public boolean match() {
if (this.text.length() == 0)
return false;
int index = 0;
for (int i = 0; i < this.text.length(); i++) {

// 先比较一次指向pattern的index与当前是否一样,一样则继续,不一样则将index往前挪
while (index > 0 && pattern.charAt(index) != text.charAt(i)) {
index = next[index - 1];
}
// 输出每次比较的情况
{
String s1 = this.text.substring(0, i) + " "
+ this.text.substring(i, i + 1) + " "
+ this.text.substring(i + 1);
String s2 = "";
for (int j = 0; j < i - index; j++)
s2 += " ";
s2 += this.pattern.substring(0, index) + " "
+ this.pattern.substring(index, index + 1) + " "
+ this.pattern.substring(index + 1);
System.out.println("i = " + i + "n" + s1 + "n" + s2 + "n");
}
if (this.text.charAt(i) == this.pattern.charAt(index)) {
index++;
if (index == this.pattern.length())
return true;
}
}
return false;
}

// 构建next数组
private void createNext() {
int m = 0;

for (int i = 1; i < this.pattern.length(); i++) {
while (m > 0 && this.pattern.charAt(i) != this.pattern.charAt(m))
m = next[m - 1];

if (pattern.charAt(m) == pattern.charAt(i))
m++;
next[i] = m;
}
}

//输出next数组
public void print() {
for (int i = 0; i < next.length; i++)
System.out.print(next[i] + " ");
System.out.println();
}

public static void main(String[] args) {
//text是要测试的文本,pattern是需要匹配的模式
String text = "abxaxbabac";
String pattern = "aba";
KMP test = new KMP(text, pattern);
test.print();
boolean match = test.match();
System.out.println(match);
}
}