LeetCode: Implement strStr()

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

   void ComputPrefix(char* pattern,int pre[], int n)  
   {  
     memset(pre, 0, n);  
     int len = 0;  
     pre[len] = 0;  
     int i = 1;  
     while(i<n)  
     {  
       if(pattern[i] == pattern[len])  
       {  
         len++;  
         pre[i]=len;  
         i++;  
       }  
       else  
       {  
         if(len>0)  
         {  
           len = pre[len-1];  
         }  
         else  
         {  
           pre[i] = 0;  
           i++;  
         }  
       }  
     }  
   }  

   char *KMP(char *haystack, char *needle)  
   {  
     int n = strlen(needle);  
     int m = strlen(haystack);  
     if(n==0)return haystack;  
     int *pre = new int[n];  
     ComputPrefix(needle, pre,n);  
     int i = 0, j = 0;  
     for (; i < m;)  
     {  
       if(haystack[i] == needle[j])  
       {  
         if(j == n-1)  
         {  
           return (&haystack[i-n+1]);  
         }  
         j++;  
         i++;  
       }  
       else  
       {  
         if(j > 0)  
           j = pre[j-1];  
         else  
         {  
           i++;  
         }  
       }  
     }  
     return NULL;  
   }  

   char *strStr(char *haystack, char *needle) {  
     return KMP(haystack,needle);  
   }