KMP算法Java实现

KMP算法Java实现

字符串模式匹配问题，是求pattern模式字符串在target目标字符串中的位置。一般的暴力求解方法时间复杂度是O（m*n），而KMP算法可以在O（n+m）的时间数量级上完成串的模式匹配。其改进在于每当一趟匹配过程中出现字符比较不相等时，不需要回溯i指针，而是利用已经得到的“部分匹配”的结果将pattern模式字符串向右滑动，继续进行比较。

这里有最通俗易懂的介绍KMP的思想：

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

Java实现

//KMP算法主函数
publicstatic int kmp(String str, String sub) {
    int j = 0;
    int[] n = next(sub);//初始化next数组
    for (int i = 0; i < str.length(); i++) {
        //如果字符不匹配，更新j的值，也就是计算往右滑动多少的过程
        while(j > 0 && str.charAt(i) !=sub.charAt(j)){
            j = n[j - 1];
        }
        if(str.charAt(i) == sub.charAt(j)){
            j++;
        }
        if(sub.length() == j){
            return i - j + 1;
        }
    }
    return -1;
}
//初始化next数组的函数
privatestatic int[] next(String sub) {
    int[] next = new int[sub.length()];
    int x = 0;
    for (int i = 1; i < sub.length(); i++) {
        while (x > 0 && sub.charAt(i) !=sub.charAt(x)) {
            x = next[x - 1];
        }
        if (sub.charAt(i) == sub.charAt(x)) {
            x++;
        }
        next[i] = x;
    }
    return next;
}
//测试
publicstatic void main(String[]args) {
    String str = "xbaabaabcacabcacba";
    String sub = "abaabcac";
    int index = kmp(str, sub);
    System.out.println(index);
}

总结

Java中String的indexOf(Stringstr)方法看源码就知道，是暴力求解实现，因为考虑到大多数的应用场景，模式串不一定存在规律，并且目标串也不一定很长，效率没什么太大差异，没必要建立一个next数组，而对于特定的问题，可以采用KMP算法。