StrStr: Find substring by using KMP algorithm

 
// http://www.mitbbs.com/article_t/JobHunting/32823417.html
// http://www.matrix67.com/blog/archives/115
class Solution {
public:
    vector<int> KMPpreprocessing(char *needle) {
         int m = strlen(needle);
         // assume j = match[i]: needle[i-j:i] == needle[0:j]
         vector<int> match(m,-1);
         int j = -1;
         for(int i=1; i<m; i++) {
             while(j>=0 && needle[i]!=needle[j+1]) j = match[j];
             if(needle[i]==needle[j+1]) j++;
             match[i] = j;
         }
         return match;
     }

     int strStr(char *haystack, char *needle) {
         if(!*needle) return 0;
         if(!*haystack) return -1;  
         int n = strlen(haystack);
         int m = strlen(needle);
         vector<int> match = KMPpreprocessing(needle);
         int j = -1;
         for(int i=0; i<n; i++) {
             while(j>=0 && haystack[i]!=needle[j+1]) j = match[j];
             if(haystack[i]==needle[j+1]) j++;
             if(j==m-1) return i-m+1;
         }
         return -1;
     }
};