Easy C++ solution using the KMP algorithm


#1
// Function to generate the LPS array of KMP algorithm
vector<int>lps_helper(string s)
{
    int n=s.length(),i=0,j=1;
    vector<int>v(n);
    v[0]=0;
    while(j<n)
    {
        if(s[i]==s[j])
        {
            v[j]=i+1;
            i++;
            j++;
        }
        else
        {
            if(i==0)
            {
                v[j]=0;
                j++;
            }
            else
            {
                i=v[i-1];
            }
        }
    }
    return v;
}
// Implementation of KMP algorithm
int kmp(string needle,string haystack)
{
    vector<int>lps=lps_helper(needle);
    int n=needle.length(),m=haystack.length(),i=0,j=0;
    // i points to needle ans j points to haystack
    while(i<n && j<m)
    {
        if(needle[i]==haystack[j])
        {
            i++;
            j++;
        }
        if(i==n)
        {
            return j-i;
        }
        else if(j<m && needle[i]!=haystack[j])
        {
            if(i==0)
            {
                j++;
            }
            else
            {
                i=lps[i-1];
            }
        }
    }
    return -1;
}
int Solution::strStr(const string haystack, const string needle) 
{
    if(needle.length()==0 || haystack.length()==0)
    {
        return -1;
    }
    return kmp(needle,haystack);
}