KMP java OMG


  • 0
    class Solution {
        public int strStr(String haystack, String needle) {
            if (needle.length() == 0) return 0;
            if (haystack.length() == 0) return -1;
            int n = needle.length();
            int[] prefix = getPrefix(needle);
            
            int i = 0, j = 0;
            int m = haystack.length();
            char[] text = haystack.toCharArray();
            char[] pattern = needle.toCharArray();
            
            while (i < m) {
                if (j == n - 1 && text[i] == pattern[j]) return i - j;
                if (text[i] == pattern[j]) {
                    i++;
                    j++;
                } else {
                    j = prefix[j];
                    if (j == -1) {
                        i++;
                        j++;
                    }
                }
            }
            return  -1;
        }
        private int[] getPrefix(String needle) {
            char[] arr = needle.toCharArray();
            int n = arr.length;
            int len = 0;
            int i = 1;
            int[] prefix = new int[n];
            prefix[0] = 0;
            
            while (i < n) {
                if (arr[i] == arr[len]) {
                    len++;
                    prefix[i] = len;
                    i++;
                } else {
                    if (len > 0) len = prefix[len - 1];
                    else {
                        prefix[i] = 0;
                        i++;
                    }
                }
            }
            
            int index = prefix.length - 1;
            while (index > 0) {
                prefix[index] = prefix[index - 1];
                index--;
            }
            prefix[0] = -1;
            return prefix;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.