C++ opyimized KMP3ms


  • 0
    E

    class Solution {
    public:
    int strStr(string haystack, string needle) {
    int len1=haystack.size(),len2=needle.size();
    int* next=(int*)malloc(sizeof(int)*(len2+1));
    get_next(needle,next,len2);
    int i=0,j=0;
    while(i<len1&&j<len2)
    {
    if(j==-1||haystack[i]==needle[j])
    {
    i++;
    j++;
    }
    else
    {
    j=next[j];
    }
    }
    if(j<len2)return -1;
    else return i-needle.size();

    }
    

    private:
    void get_next(string t, int *next,int len)
    {
    int i=0; //后缀
    int j=-1; //
    next[0]=-1;
    while(i<len)
    {
    if(j==-1||t[i]==t[j])
    {
    i++;
    j++;
    if(t[i]!=t[j])
    {
    next[i]=j;
    }
    else
    {
    next[i]=next[j];
    }
    }
    else
    {
    j=next[j];
    }
    }

        }
    

    };


Log in to reply
 

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