Share my KMP method in C++, referring to Introduction to Algorithm


  • 0
    D
    enter code here
    void generateMather(string &pattern,int *matcher)
    {
        if(!matcher)
    	    return ;
        int len=pattern.size();
        matcher[0]=0;
        matcher[1]=0;
        int k=0; //已匹配字符个数
        for(int j=2;j<=len;j++)
        {
        	while(k && pattern[k]!=pattern[j-1])
    	    	k = matcher[k];
    	    if(pattern[k]==pattern[j-1])
    	    	k++;
        	matcher[j] = k;
        }
    }
    int strStr(string haystack, string needle) {
        if(needle.size()==0)
    	    return 0;
        if(haystack.size()==0)
    	    return -1;
        int *matcher = new int[needle.size()+1];
        generateMather(needle,matcher);
        int j=0;
        for(int i=0;i<haystack.size();i++)
        {
        	while(j && needle[j]!=haystack[i])
    		    j = matcher[j];
    	    if(needle[j]==haystack[i])
    	    	j++;
    	    if(needle.size()==j)
    	    {
    	    	delete []matcher;
    		    return i-j+1;
    	    }  
        }
        delete []matcher;
        return -1;
    }

  • 0
    L

    would you please make the format right? It seems you need to click the {} before paste your code.
    Thanks


  • 0
    D

    I have re-edited it, sorry.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.