Java solution Horspool algorithm


  • 0
    Z

    I found that most of the algorithm is the KMP. So I wrote a Horspool for practise.
    The worst time complexity will be O(mn)

    public class Solution {
        int shiftTable[] = new int[128];
        
        public int strStr(String haystack, String needle) {
            char ch1[] = haystack.toCharArray();
            char ch2[] = needle.toCharArray();
            shitTable(ch2); 
            int rightend = ch1.length-1;
            int location = ch2.length-1;
            while(location <= rightend){
                int k = 0;
                while(k <= ch2.length-1 && ch2[ch2.length-1-k] == ch1[location-k]){
                    k ++;
                }
                if(k == ch2.length){
                    return location-k+1;
                }else{
                    location = shiftTable[ch1[location]] + location;
                }
            }
            return -1;
        }
        
        public void shitTable(char[] pattern){
            for(int i=0;i < shiftTable.length;i ++){
                shiftTable[i] = pattern.length;
            }
            for(int i=0;i < pattern.length-1;i ++){
                shiftTable[pattern[i]] = pattern.length-i-1;
            }
        }
    }
    

Log in to reply
 

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