KMP算法模版

KMP算法模版（左神的程序员代码面试指南第二版KMP算法）

public class KMP {

    /**
     * @param s 匹配串
     * @param m 模式串
     * @return 匹配成功返回匹配串的匹配成功的字符串首个位置，匹配失败返回-1
     */
    public int getIndexOf(String s, String m) {
        if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
            return -1;
        }

        char[] ss = s.toCharArray();
        char[] ms = m.toCharArray();

        int si = 0;
        int mi = 0;

        int[] next = getNextArray(ms);

        while (si < ss.length && mi < ms.length) {
            if (ss[si] == ms[mi]) {
                si++;
                mi++;
            } else if (next[mi] == -1) {
                si++;
            } else {
                mi = next[mi];
            }
        }

        return mi == ms.length ? si - mi : -1;
    }

    /**
     * 获得next数组
     *
     * @param ms 模式串
     * @return 返回next数组
     */
    public int[] getNextArray(char[] ms) {
        if (ms.length == 1) {
            return new int[]{-1};
        }

        int[] next = new int[ms.length];
        next[0] = -1;
        next[1] = 0;

        int pos = 2;
        int cn = 0;

        while (pos < next.length) {
            if (ms[pos - 1] == ms[cn]) {
                next[pos++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[pos++] = 0;
            }
        }
        return next;
    }

    public static void main(String[] args) {
        KMP kmp = new KMP();
        System.out.println(kmp.getIndexOf("acbc", "bc"));
        System.out.println(kmp.getIndexOf("acbc", "bcc"));
    }
}