Leetcode 28 Implement strStr()

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Update (2014-11-02):
The signature of the function had been updated to return the index instead of the pointer. If you still see your function signature returns a char * or String, please click the reload button  to reset your code definition.

Solution 1: Use brute force. two pointers.

 public class Solution {  
   public int strStr(String haystack, String needle) {  
     int n=haystack.length(), m=needle.length();  
     if (m==0) return 0;  
     int i=0, j=0;  
     while (i<n && j<m) {  
       if (haystack.charAt(i)==needle.charAt(j)) {  
         i++;  
         j++;  
       }  
       else {  
         i=i-j+1;  
         j=0;  
       }  
     }  
     if (j==m) return i-m;  
     return -1;  
   }  
 }  

Solution 2: KMP

 public class Solution {  
   public int strStr(String haystack, String needle) {  
     int n=haystack.length(), m=needle.length();  
     if (m==0) return 0;  
     int[] next=new int[m];  
     next[0]=-1;  
     int j=0, k=-1;  
     while (j<m-1) {  
       if (k==-1 || needle.charAt(j)==needle.charAt(k)) {  
         k++;  
         j++;  
         next[j]=(needle.charAt(j)==needle.charAt(k))?next[k]:k;  
       }  
       else k=next[k];  
     }  
     int i=0;  
     j=0;  
     while (i<n && j<m) {  
       if (j==-1 || haystack.charAt(i)==needle.charAt(j)) {  
         i++;  
         j++;  
       }  
       else j=next[j];  
     }  
     if (j==m) return i-m;  
     return -1;  
   }  
 }