学步园

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是基本功啊！但还是一下init里有个地方写错，牢记啊牢记！！

class Solution {
public:
    char *strStr(char *hay, char *need) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        if ( !hay || !need  )
	    	return NULL;
	    int nH=strlen(hay);
	    int nN=strlen(need);
	    if ( nN >nH )
		    return NULL;
	    if (nN==0)
		    return hay;

	    vector<int> pre(nN,-1);
	    init(pre,need,nN);
	    int pN=-1;
	    for(int pH=-1;pH<nH;pH++)
	    {
		    while(pN!=-1&&hay[pH+1]!=need[pN+1])
			    pN=pre[pN];
		    if(hay[pH+1]==need[pN+1])
			    pN++;
		    if ( pN == nN-1 )
			    return &hay[pH-nN+2];
	    }
	    return NULL;
    }
    void init(vector<int>& pre,char* s,int n)
    {
	    int p;
	    pre[0]=-1;
	    for(int i=1;i<n;i++)
	    {
		    p=pre[i-1];
		    while(p!=-1&&s[p+1]!=s[i])
			    p=pre[p];
		    if ( s[p+1]==s[i])
			    pre[i]=p+1;
		    else
			    pre[i]=-1;
	    }
    }
};