public class _28 {
    static class Solution {
        public int strStr(String haystack, String needle) {
            if (needle.length() == 0) return 0;
            return kmp(haystack.toCharArray(), needle.toCharArray());
        }

        public int kmp(char[] m, char[] p) {
            //构建table
            int k = 0;
            int[] table = new int[p.length];
            for (int i = 1; i < p.length; i++) {
                while (k > 0 && p[k] != p[i]) {
                    k = table[k - 1];
                }
                if (p[k] == p[i]) {
                    k++;
                }
                table[i] = k;

            }
            int x = 0;
            for (int i = 0; i < m.length; i++) {
                while (x > 0 && p[x] != m[i]) {
                    x = table[x - 1];
                }
                if (p[x] == m[i]) x++;
                if (x == p.length) {
                    return i - x + 1;
                }
            }
            return -1;
        }
    }
}