class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        String s = needle + "#" + haystack;
        int[] pi = new int[s.length()];

        for (int i = 1; i < s.length(); i++) {
            int len = pi[i - 1];
            while (len > 0 && s.charAt(i) != s.charAt(len)) {
                len = pi[len - 1];
            }
            if (s.charAt(i) == s.charAt(len)) {
                pi[i] = len + 1;
                if (pi[i] == m) {
                    return i - m * 2;
                }
            }
        }
        return -1;
    }
}