KMP Solution by Java


  • 0
    A
    class Solution {
        public int strStr(String haystack, String needle) {
            if(needle.length() == 0)return 0;
            if(haystack.length()<=needle.length() && !haystack.equals(needle))return -1;
            
            char[] str = haystack.toCharArray();
            char[] ms = needle.toCharArray();
            
            return getIndex(str, ms);
        }
        
        public int getIndex(char[] str, char[] ms){
            
            int[] next = getNext(ms);
            
            int index = 0;
            for(int i=0; i<str.length; i++){
                while(index>0 && str[i]!=ms[index]){
                    index = next[index];
                }
                if(index == -1)index = 0;
    
                if(str[i] == ms[index])index++;
                if(index == ms.length)return i-index+1;
            }
    
    
            return -1;
        }
    
        public int[] getNext(char[] ms){
            if(ms.length == 1)return new int[]{-1};
    
            int[] next = new int[ms.length];
            next[0] = -1;
            next[1] = 0;
            int pos = 2;
            int cn = 0;
            while(pos < ms.length){
                if(ms[pos-1] == ms[cn]){
                    next[pos++] = ++cn;
                }else if(cn > 0){
                    cn = next[cn];
                }else{
                    next[pos++] = 0;
                }
            }
    
            return next;
        }
    
    }
    

Log in to reply
 

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