KMP solution with C++


  • 0
    I

    This link will help you to understand it.

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

Log in to reply
 

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