Share my C++ 4ms solution, using KMP algorithm


  • 0
    J
    class Solution {
    public:
    int strStr(string haystack, string needle) {
        int n=haystack.length();
        int m=needle.length();
        if (m==0)
            return 0;
        //build table
        int *table=new int [m];
        table[0]=-1;
        for (int i=1;i<m;++i)
        {
            int j=table[i-1];
            while (j>=0 && needle[j]!=needle[i-1])
            {
                j=table[j];
            }
            if (j==-1)
                table[i]=0;
            else
                table[i]=j+1;
        }
        //search
        int i=0,j=0;
        while (i<n)
        {
            if (haystack[i]==needle[j])
            {
                i++;
                j++;
                if (j==m)
                    return i-m;
            }
            else
            {
                j=table[j];
                if (j==-1)
                {
                    j++;
                    i++;
                }
            }
        }
        return -1;
    }
    };

Log in to reply
 

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