模式匹配的KMP算法

来源：《数据结构：使用C++语言描述》

　　

代码：

参考：https://blog.csdn.net/scgaliguodong123_/article/details/49148017

模式匹配的KMP算法：
　　比简单模式匹配算法多了个失败函数，利用失败数组next去除匹配过程中毫无意义的回溯对比。

public class KMPMatch {
    /**
     * @param s 主串
     * @param t 子串
     * @param pos 从主串的pos下标开始进行模式匹配
     * @return
     */
    public int indexKMP(String s, String t, int pos) {

        int i = pos; //下标i指向主串（只进不退）
        int j = 0; //下标j指向子串（若匹配失败就退回到“合适的”位置）

        int[] next = getNext(t); //由子串t获构建 失败数组next

        while (i < s.length() && j < t.length()) {
            if (j == -1 || s.charAt(i) == t.charAt(j)) { 
                i++;
                j++;
            } else { //匹配失败，重新进行匹配
                j = next[j]; //下标j退回到合适的位置，i值不变
            }
        }
        if (j >= t.length()) {
            return i - t.length();
        } else {
            return 0;
        }
    }

// 失败函数

/**
 * 失败函数：构建“失败next数组”
 *   设长度为m的子串T="t1t2...t(m-1)"，k为相同的前、后缀子串长，next数组定义为
 *            
 *           |--> -1, 当j=0时
 *   next[j]=|--> max{ k|0<k<j且 t1 t2 ... t(k-1) = t(j-k) t(j-k+1) ... t(j-1)}
 *           |--> 0, 其他情况
 * @param t 子串
 * @return
 */
public int[] getNext(String t) {
    int[] next = new int[t.length()];
    int i = 0;
    int j = -1;

    next[i] = j; //令next[0]=-1

    while (i < t.length()-1) {
        if (j == -1 || t.charAt(i) == t.charAt(j)) {
            i++;
            j++;
            next[i] = j; //初次next[1]=0
        } else {
            j = next[j]; //若字符不相等，则j值进行回溯
        }
    }
    //将next数组打印出来，看看是什么样子的
    System.out.println(Arrays.toString(next));

    return next;
}

// 测试

    public static void main(String[] args) {
        KMPMatch test = new KMPMatch();
        System.out.println(test.indexKMP("goodgoogle", "google", 0));

    }
}