package com.logi.algorithm;
public class KMPReview {
public static void main(String[] args) {
String text = "This a simple example!";
String pattern = "simple";
System.out.println(text);
for (int i = 0; i < new KMPReview().indexOf(text, pattern); i++) {
System.out.print(" ");
}
System.out.println(pattern);
}
public void buildMatch(String pattern, int[] match) {
match[0] = -1;
int i;
for (int j = 1; j < pattern.length(); j++) {
i = match[j - 1];
while (i >= 0 && pattern.charAt(i + 1) != pattern.charAt(j)) {
i = match[i];
}
if (pattern.charAt(i + 1) == pattern.charAt(j)) {
match[j] = i + 1;
} else {
match[j] = -1;
}
}
}
public int indexOf(String text, String pattern) {
if (text.length() < pattern.length()) {
return -1;
}
int[] match = new int[pattern.length()];
this.buildMatch(pattern, match);
int t = 0, p = 0;
while (t < text.length() && p < pattern.length()) {
if (text.charAt(t) == pattern.charAt(p)) {
t++;
p++;
} else if (p > 0) {
p = match[p - 1] + 1;
} else {
t++;
}
}
return p == pattern.length() ? t - p : -1;
}
}
如有问题请在下方留言,文章转载请注明出处,详细交流请加下方群组!请大佬不要屏蔽文中广告,因为它将帮我分担服务器开支,如果能帮忙点击我将万分感谢。