精華之處：求next數(shù)組（自動(dòng)機(jī)）
KMP與getNext方法相同，只有?next[suffix] = prefix;? //1不同
next數(shù)組求解方法：
1.覆蓋表：求前綴、后綴公共部分最大長度
2.next數(shù)組為覆蓋表右移一位。
public class KMP {
? ? public static int KMP(String s, String t) {
? ? ? ? int i = 0;
? ? ? ? int j = 0;
? ? ? ? //得到next數(shù)組
? ? ? ? int[] next = getNext(t);
? ? ? ? while (i < s.length() && j < t.length()) {
? ? ? ? ? ? if (j == -1 || s.charAt(i) == t.charAt(j)) {
? ? ? ? ? ? ? ? i++;
? ? ? ? ? ? ? ? j++;
? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? //根據(jù)next數(shù)組的指示j進(jìn)行回溯，而i永遠(yuǎn)不會(huì)回溯
? ? ? ? ? ? ? ? j = next[j];
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if (j == t.length()) {
? ? ? ? ? ? return i - j;
? ? ? ? }else {
? ? ? ? ? ? return -1;
? ? ? ? }
? ? }
? ? /**
?? ? * next指的是KMP主算法中的j該回溯到哪個(gè)位置
?? ? *其值就是當(dāng)前位置之前的可覆蓋子串最大長度；
?? ? *
?? ? *所以代碼就是找可覆蓋子串的最大長度，
?? ? *其實(shí)就是：模式串自己對自己的匹配
?? ? *用prefix所指的串去匹配suffix所指的串
?? ? *所以代碼和kmp的主算法是類似的
?? ? * @param t
?? ? * @return
?? ? */
? ? public static int[] getNext(String t) {
? ? ? ? int[] next = new int[t.length()];
? ? ? ? next[0] = -1;
? ? ? ? int suffix = 0;? // 后綴
? ? ? ? int prefix = -1;? // 前綴
? ? ? ? while (suffix < t.length() - 1) {
? ? ? ? ? ? //若前綴索引為-1或相等，則前綴后綴索引均+1
? ? ? ? ? ? if (prefix == -1 || t.charAt(prefix) == t.charAt(suffix)) {
? ? ? ? ? ? ? ? ++prefix;
? ? ? ? ? ? ? ? ++suffix;
? ? ? ? ? ? ? ? next[suffix] = prefix;? //1
? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? prefix = next[prefix];? //2
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return next;
? ? }
? ? /**
?? ? *改進(jìn)的就是可覆蓋子串的后一項(xiàng)，可能和當(dāng)前項(xiàng)一樣
?? ? *如ABCDABD,第二個(gè)AB不該是0，1，而是-1，0
?? ? * @param t
?? ? * @return
?? ? */
? ? public static int[] getNext2(String t) {
? ? ? ? int[] next = new int[t.length()];
? ? ? ? next[0] = -1;
? ? ? ? int suffix = 0;? // 后綴
? ? ? ? int prefix = -1;? // 前綴
? ? ? ? while (suffix < t.length() - 1) {
? ? ? ? ? ? //若相等或前綴索引為-1，則前綴后綴索引均+1
? ? ? ? ? ? if (prefix == -1 || t.charAt(prefix) == t.charAt(suffix)) {
? ? ? ? ? ? ? ? ++prefix;
? ? ? ? ? ? ? ? ++suffix;
? ? ? ? ? ? ? ? //改進(jìn)的地方
? ? ? ? ? ? ? ? if (t.charAt(prefix) == t.charAt(suffix)) {
? ? ? ? ? ? ? ? ? ? next[suffix] = next[prefix];
? ? ? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? ? ? next[suffix] = prefix;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? prefix = next[prefix];
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return next;
? ? }
}
