KMP solution in Java


  • 5
    S

    Hi guys!

    Here is a pretty concise implementation of a Knuth-Morris-Pratt algorithm in Java.
    Instead of commenting and explaining the approach I want to give a really-really useful link to TopCoder tutorial on the topic. The code is just a slightly modified version of the code from the tutorial and an explanation there is perfect.


    public class Solution {
        
        private int[] failureFunction(char[] str) {
            int[] f = new int[str.length+1];
            for (int i = 2; i < f.length; i++) {
                int j = f[i-1];
                while (j > 0 && str[j] != str[i-1]) j = f[j];
                if (j > 0 || str[j] == str[i-1]) f[i] = j+1;
            }
            return f;
        }
    
        public int strStr(String haystack, String needle) {
            if (needle.length() == 0) return 0;
            if (needle.length() <= haystack.length()) {
                int[] f = failureFunction(needle.toCharArray());
                int i = 0, j = 0;
                while (i < haystack.length()) {
                    if (haystack.charAt(i) == needle.charAt(j)) {
                        i++; j++;
                        if (j == needle.length()) return i-j;
                    } else if (j > 0) j = f[j];
                    else i++;
                }
            }
            return -1;
        }
    }
    

  • 2
    K

    Thanks for bringing up kmp algorithm, and I found a much better explanation here
    http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/
    for ppl can't get their heads around "the prefix of the suffix of the prefix of the…"


Log in to reply
 

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