KMP by java


  • 2
    P
    public int kmp(char[] s, char[] p) {
            int[] table = prefix(p);
            int j = -1;
            for (int i = 0; i < s.length; i++) {
                if (s[i] != p[j + 1]) {
                    while(j > -1 && s[i] != p[j + 1]) j = table[j];
                }
                if(s[i] == p[j + 1]) j++;
                if(j == p.length - 1) return i - p.length + 1;
            }
            return -1;
        }
    
        public int[] prefix(char[] array) {
            int[] ans = new int[array.length];
            ans[0] = -1;
            int k = -1;
            for (int i = 1; i < array.length; i++) {
                while(k > -1 && array[k + 1] != array[i]) k = ans[k];
                if (array[k + 1] == array[i]) k++;
                ans[i] = k;
            }
            return ans;
        }
    

    just call kmp.


Log in to reply
 

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