public class KmpAlgorithm {
public static void main(String[] args) {
String str1 = "C\t C\tC\tC\tC\tC\tC\tC\tC\tA\tA\tA\tA\tB\tA\tA\tA\tA\tB\t A\tB\tB\tC\tA\tB\tB\tC\tA\tA\tA\tB\tB\tC\tA\tB\tB"
.replace("\t", "")
.replace(" ", "");
String str2 = "AAABAAAAB";
int[] next = kmpNext(str2);
for (int i = 0; i < next.length; i++) {
System.out.print(str2.charAt(i) + "\t");
}
System.out.println();
for (int i = 0; i < next.length; i++) {
System.out.print(next[i] + "\t");
}
System.out.println();
System.out.println("====================");
int index = kmpSearch(str1, str2, next);
System.out.println(index);
}
public static int kmpSearch(String str1, String str2, int[] next) {
for (int i = 0, j = 0; i < str1.length(); i++) {
while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
j = next[j - 1];
}
if (str1.charAt(i) == str2.charAt(j)) {
j++;
}
if (j == str2.length()) {
return i - (j - 1);
}
}
return -1;
}
public static int[] kmpNext(String dest) {
int[] next = new int[dest.length()];
for (int i = 1, j = 0; i < dest.length(); i++) {
while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
j = next[j - 1];
}
if (dest.charAt(i) == dest.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
}
程序就不看了,但是就从语法的角度来说
任何while循环都可以机械地改成if + 递归。