use KMP algorithms to solve this problem!


  • 0
    T
    public class Solution {
        public int strStr(String haystack, String needle) {
              if(needle==null || needle.length()<1){
                  return 0;
              }
              int[] dp=constructKMP(needle);
              int i=0;
              int j=0;
              
              char[] h_array=haystack.toCharArray();
              char[] n_array=needle.toCharArray();
              while(i<haystack.length()){
                  if(h_array[i]==n_array[j]){
                      i++;
                      j++;
                      if(j==n_array.length){
                          return i-n_array.length;
                      }
                  }else{
                      if(j!=0){
                          j=dp[j-1];
                      }else{
                          i++;
                      }
                  }
              }
              
              return -1;
        }
        
        public int[] constructKMP(String needle){
            char[] array=needle.toCharArray();
            int[] dp=new int[array.length];
            int i=0;
            int j=1;
            
            dp[0]=0;
            while(i<array.length&&j<array.length){
                if(array[i]==array[j]){
                    dp[j]=i+1;
                    i++;
                    j++;
                }else{
                    if(i!=0){
                        i=dp[i-1];
                    }else{
                        dp[j]=0;
                        j++;
                    }
                }
            }
            
            return dp;
        }
    }
    

Log in to reply
 

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