My c++ code with KMP


  • 0
    1

    Here is my c++ code with KMP to solve this problem, I just learned KMP recently, the return value of the function has been changed to the index of the sub string.

    class Solution {
    public:
        int strStr(char *haystack, char *needle) {
            int lenh = strlen(haystack), lenn = strlen(needle);
            if(lenn==0) return 0;
            int *next = new int[lenn];
            getNext(needle,next);
            int i = 0, j = 0, index = -1;
            while(i<lenh&&j<lenn)
            {
                if(j==-1||haystack[i]==needle[j])
                {
                    i++;
                    j++;
                    if(j==lenn) 
                    {
                        index = i-lenn;
                        break;
                    }
                }
                else if(haystack[i]!=needle[j])
                {
                    j = next[j];
                }
            }
            return index;
        }
        
        void getNext(char *p,int *next)
        {
            int len = strlen(p);
            int i = 0, k = -1;
            next[0] = -1;
            while(i<len-1)
            {
                if(k==-1||p[k]==p[i])
                {
                    k++;
                    i++;
                    next[i] = k;
                }
                else
                {
                    k = next[k];
                }
            }
        }
    };

Log in to reply
 

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