Knuth-Morris-Pratt Algorithm Implementation Part-1

Just recently we encountered a problem to implement the method strStr(). (You may view the full question here.) The preferred solution is the implementation of the Knuth-Morris-Pratt algorithm. Here is an attempt at doing that —

If CLRS was not enough, there is a plethora of brilliant sources online. Here is one, just a click away. Once you have grasped the idea, let’s proceed to the next step of breaking down our problem:

• Build the skip table — Proper prefixes and proper suffixes
• Iterate through the haystack keeping in mind to avoid redundant checks with the help of the skip table

This part deals with the building of the skip table —

private HashMap<Integer, Integer> getSkipTable(String needle){
        int size = needle.length();
        HashMap<Integer, Integer>  skipTable = new HashMap<>();
        for(int i = 0; i<size; i++){
            String pattern = needle.substring(0,i+1);
            skipTable.put(i, findTableVal(pattern));
        }
        return skipTable;
    }
    
    private int findTableVal(String pattern){
        HashSet pre = getProperPrefixes(pattern);
        HashMap suf = getProperSuffixes(pattern);
        
        for(int i = pattern.length(); i>0; i--){
            if(suf.containsKey(i)){
                if(pre.contains(suf.get(i))){
                    return i;
                }
            }
        }
        return 0;
    }
    
    private HashSet<String> getProperPrefixes(String pattern){
        //value of the proper suffix for the given sub-pattern
        HashSet<String> set = new HashSet();
        int size = pattern.length();
        for(int i = 1; i<=(size-1); i++){
            set.add(pattern.substring(0, i));
        }
        return set;
    }
    
    private HashMap<Integer, String> getProperSuffixes(String pattern){
        //key is the length of the proper prefix of the sub-pattern
        //value is the actual prefix string of the sub-pattern
        HashMap<Integer, String> map = new HashMap<>();
        int size = pattern.length();
        for(int i = 1; i<size; i++){
            map.put(size-i, pattern.substring(i, size));
        }
        return map;
    }

See you in the next post.

Cheers & Chao!