Implement strStr()

Implement strStr().

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

思路：

KMP算法。

这道题理解KMP花了很久的时间，在求next函数的时候使用递推的思路，假如a[i] = k, 如果a[i+1] = a[k]，那么a[i+2] != a[k+1]时，a[i+1] = k+1, 否则k = next[k]，相当于在已匹配的子串部分再使用KMP。理解这一部分就基本理解全部了。

代码：

    void getNext(char *needle, int length, int *next){
        next[0] = -1;
        int k = -1;
        int i = 0;
        while(i < length-1){
            if(k == -1 || needle[i] == needle[k]){
                k++;
                i++;
                if(needle[i] != needle[k])
                    next[i] = k;
                else
                    next[i] = next[k];
            }
            else
                k = next[k];
        }
    }
    char *strStr(char *haystack, char *needle) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        int lh = strlen(haystack), ln = strlen(needle); 
        if(ln == 0 || lh == 0)
            return NULL;
        int *next = new int[ln];
        getNext(needle, ln, next);
        int i=0,j=0;
        while(i < lh && j < ln){
            if(haystack[i] == needle[j]){
                i++; 
                j++;
            }
            else{
                j = next[j];
                if(j == -1){
                    j = 0;
                    i++;
                }
            }
        }
        delete[] next;
        if(j == ln){
            return haystack+i-ln;
        }
        else
            return NULL;
    }