以前学习数据结构的时候，有关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);
}
}
No comments:
Post a Comment