java实现的KMP算法

public class KMPAlgorithm { 

 

    /**

     * 计算模式串的next函数

     * 

     * @param desStr

     *            模式串

     * @return 模式串的next函数，用数组来保存

     */ 

    private static int[] kmpNext(String desStr) { 

        int len = desStr.length(); 

        int i = 0; 

        int j = -1; 

        int next[] = new int[len]; 

        while (i < len - 1) { 

            if (j == -1 || (desStr.charAt(i) == (desStr.charAt(j)))) { 

                i++; 

                j++; 

                if (desStr.charAt(i) != (desStr.charAt(j))) { 

                    next[i] = (j + 1); 

                } else { 

                    next[i] = next[j]; 

                } 

            } else { 

                j = (next[j] - 1); 

            } 

        } 

        return next; 

 

    } 

 

    /**

     * kmp的核心算法

     * 

     * @param sourceStr

     * @param desStr

     * @param pos

     *            从主串的第几个字符开始匹配

     * @return 成功的话返回位置，失败的话返回-1，索引从0开始的

     */ 

    public static int index(String sourceStr, String desStr, int pos) { 

        int next[] = kmpNext(desStr); 

        int i = 0; 

        int j = 0; 

        while (i < sourceStr.length() - 1 && j < desStr.length() - 1) { 

            if (j == 0 || (sourceStr.charAt(i) == desStr.charAt(j))) { 

                i++; 

                j++; 

            } else 

                j = (next[j] - 1); 

        } 

        if (j > desStr.length() - 2) { 

            return (i - desStr.length() + 1); 

        } else 

            return -1; 

 

    } 

 

}