Share my JAVA KMP solution, and can somebody tell me why my KMP is worse than those brute force solutions


  • 0
    U

    Hey here is my java KMP solution

        public int strStr(String haystack, String needle) {
            if(needle.length() == 0) return 0;
            int T[] = new int[needle.length()];
            char[] needleArray = needle.toCharArray();
            char[] haystackArray = haystack.toCharArray();
            
            int offset = 0;
            //Build table O(n)
            for(int i = 1 ; i < needle.length() ; ){
                //Fill trace length (where suffix == prefix) in T[]
                if(i+offset< needle.length() && needleArray[i+offset] == needleArray[offset]){
                    T[i+offset] = T[i+offset-1]+1;
                    offset++;
                }
                else{
                    //prefix-suffix diff then move i to the end of suffix
                    i = i+offset+1;
                    offset = 0;
                }
            }
            
            
    
            int m = 0;
            int i = 0;
            
            //O(n) for matching based on table
            for(i = 0 ; (i+m) < haystack.length() ; ){
                //Handle equal case
                if(haystackArray[i+m] == needleArray[m]){
                    //We just matched them all
                    if(m == needle.length()-1){
                        return i;
                    }
                    m++;
                }
                //Handle not equal case
                else{
                    if(m == 0){
                        //letters at beginning are different then move back i by 1;
                        i++;
                    }
                    else{
                        //trace back
                        i += m - T[m-1];
                        m = T[m-1];
                    }
                }
            }
            
            return -1;
        }
    }
    

    The result is 8ms, and only beat 23% of the accepted submissions. Most solutions with 5 or less ms from my point of view are O(n^2). Can any one tell me how my code can be optimized?


Log in to reply
 

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