KMP算法Java实现

<span style="font-family:Courier New;">package com.dxinl.kmp;

import java.util.Scanner;

public class KMP {
public static void main(String[] args) {
new KMP();
}

public KMP() {
Scanner scanner = new Scanner(System.in);
System.out.println("Please Input the longer String Text:");
String text = scanner.nextLine();

System.out.println("Please Input the shorter String Pattern:");
String pattern = scanner.nextLine();
scanner.close();

int[] next = getNext(pattern);
System.out.println("next[]:");
for (int i = 0; i < next.length; i++) {
System.out.print(next[i] + " ");
}
System.out.println();

int i = 0, j = 0;
while (i <= text.length() - pattern.length()) {
while (j == -1 || j < pattern.length() && text.charAt(i) == pattern.charAt(j)) {
i ++;
j ++;
}
if (j == pattern.length()) {
System.out.println(i - pattern.length());
return;
}
j = next[j];
}

System.out.println("no match");
}

private int[] getNext(String pattern) {
int[] next = new int[pattern.length()];
int j = -1, i = 0;
next[0] = -1;

while (i < pattern.length() - 1) {
if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}

return next;
}
}


参考：http://www.cnblogs.com/10jschen/archive/2012/08/21/2648451.html
      数据结构与算法-Java语言版(第2版) chapter 13

附上《数据结构与算法-Java语言版(第2版)》KMP算法的图例：
字符串Text：ababcdabbabababad
   pattern：abababa
第一次匹配：
           i
           ↓
   a b a b c d a b b a b a b a b a d
   a b a b a b a
           ↑
           j
第二次匹配：
           i
           ↓
   a b a b c d a b b a b a b a b a d
       a b a b a b a
           ↑
           j
……………………
next[j] = -1                                                            for j = 0
next[j] = max{k:0 < k < j and pattern[0...k-1] = pattern[j-k...j-1]}    if such a k exists
next[j] = 0                                                             otherwise
</span>