Java KMP Solution


  • 0
    M
    class Solution {
       public int strStr(String haystack, String needle) {
                
           int index = 0;
           int i=0,j=0;
           
           if(needle.length() > haystack.length()){
               return -1;
           }
           
           if(needle.length()==0){
               return 0;
           }
                  
           int[] lps = getLps(needle.toCharArray());
           
           while(i<haystack.length() && j<needle.length()){
               
               if(haystack.charAt(i) == needle.charAt(j)){
                   if(j==0){
                       index=i;
                   }
                   i++;
                   j++;
               }
               
               else {
                   if(j==0){
                       i++;
                   }
                   else {
                       j=lps[j-1];
                       index = i-j;
                   }
               } 
               
           }
           
           if(j==needle.length()){
               return index;
           } else {
               return -1;
           }
           
        }
        
        private int[] getLps(char[] pattern) {
            
            int[] arr = new int[pattern.length];
            int j=0;
            for(int i=1; i<pattern.length;){
                
                if(pattern[i] == pattern[j]){
                    arr[i] = j+1;
                    i++;
                    j++;
                } else { 
                    if(j==0){
                        arr[i] = 0;
                        i++;
                    } else {
                        j=arr[j-1];
                    }
                    
                }   
            }
            return arr;
        }
    }
    

Log in to reply
 

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