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.

KMP算法的应用

class Solution 
{
public:
    int strStr(char *haystack, char *needle) 
    {
        if(haystack == NULL)
            return -1;
        string hs="";
        string ns="";
        int n=0;
        int m=0;
        while(haystack[n] != '\0')
        {
            hs += haystack[n];
            n++;
        }
        if(needle == NULL)
            return -1;
         while(needle[m] != '\0')
        {
            ns += needle[m];
            m++;
        }
        if( m==0 && n==0)
            return 0;
        if(n==0)
            return -1;
        if(m==0)
            return 0;
        if(m>n)
            return -1;
        int* next = new int[m];
        get_next(needle,next,m);
        int i=0,j=0;
        while(i<n && j<m)
        {
            if(j<0 || hs[i] == ns[j])
            {
                i++;
                j++;
            }
            else
                j = next[j];
        }
        if(j==m)
            return i-j;
        else
            return -1;
    }
    void get_next(char* needle, int* next, int n)
    {
        int i=1;
        next[0] = -1;
        while(i<n)
        {
            int k = next[i-1];
            while(k>=0 && needle[k] != needle[i-1])
                k = next[k];
            if(k<0)
                next[i] = 0;
            else
                next[i] = k+1;
            i++;
        }
    }
};

LeetCode--Implement strStr()