8.Implement strStr()

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Pattern Searching

Example 1:
Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1

Solution I: (Bruteforce)

class Solution
{
public:
    int strStr(string haystack, string needle)
    {

        int ndl_len = needle.length();

        if (ndl_len == 0)
        {
            return 0;
        }
        else if (haystack.length() == 0 || ndl_len > haystack.length())
        {
            return -1;
        }

        char first_char = needle[0];
        int pos = -1;
        for (int i = 0; i <= haystack.length() - ndl_len; i++)
        {

            if (haystack[i] == first_char)
            {
                string sub = haystack.substr(i, ndl_len);
                if (sub == needle)
                {
                    pos = i;
                    break;
                }
            }
        }

        return pos;
    }
};

Time Complexity: O(n * m)

Solution II (Using KMP Algo):

class Solution
{
public:
    vector<int> computeLPS(vector<int> &lps, int len, string pat)
    {
        int i = 0;
        int j = 1;
        lps[0] = 0;
        while (j < len)
        {
            if (pat[i] == pat[j])
            {
                lps[j] = i + 1;
                i++;
                j++;
               
            }
            else
            {
                if (i != 0)
                {
                    i--;
                    i = lps[i];
                }
                else
                {
                    lps[j] = 0;
                    j++;
                }
            }
        }

        return lps;
    }

    int strStr(string s, string pattern)
    {
        if(pattern==""){return 0;}
        if(s=="" && pattern!=""){return -1;}

        int l = pattern.length();
        vector<int> lps(l);
        int res = -1;
        int i = 0, j = 0;
        
        lps = computeLPS(lps, l, pattern);
        
        while (i < s.length())
        {

            if (s[i] == pattern[j])
            {
                i++;
                j++;
            }

            if (j == pattern.length())
            {
                res = i-j;
                break;
            }
            else if (i < s.length() && s[i] != pattern[j])
            {
                if (j != 0)
                {
                    j--;
                    j = lps[j];
                }
                else
                {
                    i++;
                }
            }
        }
        
        return res;
    }
};

Time Complexity: O(n + m)

Solution III : (Rabin Krap Algo)

class Solution
{
public:
    int computeHash(string pattern, int prime, int len)
    {
        int s = 0;
        for (int i = 0; i < len; i++)
        {
            s = s + (pattern[i] - 96) * pow(prime, i);
        }
        return s;
    }

    int recomputeHash(string pattern, int prime, int start, int end, int prevHash, int len)
    {
        int s = prevHash;
        s = s - (pattern[start] - 96);
        s = s / prime;
        s = s + (pattern[end] -96 ) * pow(prime, len - 1);
        return s;
    }

    bool isEqual(string pattern, string text, int start, int end)
    {
        int i = 0;
        while (start < end)
        {
            if (pattern[i] != text[start])
            {
                return false;
            }
            i++;
            start++;
        }
        return true;
    }

    int strStr(string text, string pattern)
    {

        int m = pattern.length();
        int n = text.length();
        int prime = 1;
        int hash = computeHash(pattern, prime, m);

        int textHash = computeHash(text, prime, m);

        for (int i = 0; i <= n - m; i++)
        {
            if (textHash == hash)
            {
                if (isEqual(pattern, text, i, i + m))
                {
                    return i;
                }
            }
            else
            {
                textHash = recomputeHash(text, prime, i, i+m,textHash, m);
            }
        }

        return -1;
    }
};

Time Complexity: O(n + m)