KMP

[sync-by-unito[bot]]

//28. Implement strStr()

┆Issue is synchronized with this Trello card by Unito

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//28. Implement strStr()

class Solution_q28_b { //KMP: https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/ //https://www.youtube.com/watch?v=BXCEFAzhxGY public: std::vector computeLPS(std::string pat) { int n = pat.size(); std::vector lps(n, 0);

    int len = 0, i = 1;
    while (i<n) {
        if (pat[len] == pat[i]) {
            lps[i++] = ++len;
        }
        else { //(pat[len] != pat[i])
            // Consider the example. 
            // AAACAAAA and i = 7. The idea is similar to search step. 
            if (len != 0) { 
                len = lps[len - 1]; //reset the longest proper prefix length
                //note that we do not increment i here 
            }
            else { // if (len == 0) 
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}
int strStr(std::string haystack, std::string pat) {
    //pre-req:
    int m = haystack.size();
    int n = pat.size();
    if (n == 0) return 0;

    std::vector<int> lps = computeLPS(pat);
    int i = 0, j = 0;
    while (i < m) {
        if (haystack[i] == pat[j]) {
            i++; j++;
        }
        if (j==n) { //matched length == pat.size(), we found one fully matched.
            //print or return here.
            //for strStr, return i-j;
            return i - j;
            //for printing all, j=lps[j-1], print.
            //std::cout << i - j << ",";
            //j = lps[j - 1];
        }
        if (i < m && haystack[i] != pat[j]) { // mismatch after j matches 
            // Do not match lps[0..lps[j-1]] characters, they will match anyway 
            if (j == 0)
                i++;
            else
                j = lps[j - 1];
        }
    }
    return -1;
}

};

[sync-by-unito[bot]]

➤ Nelson 3513 commented:

//214. Shortest Palindrome

https://leetcode.com/problems/shortest-palindrome/discuss/60113/Clean-KMP-solution-with-super-detailed-explanation The trick is to build a temp string like this: s + "#" + reverse(s)

Then we run KMP on it, the value in last cell will be our solution. In this problem, we don't need to use KMP to match strings but instead we use the lookup table in KMP to find the palindrome.

We add "#" here to force the match in reverse(s) starts from its first index What we do in KMP here is trying to find a match between prefix in s and a postfix in reverse(s). The match part will be palindrome substring.

Example: input: catacb Temp String: catacb # bcatac

KMP table: c a t a c b # b c a t a c 0 0 0 0 1 0 0 0 1 2 3 4 5

In the last cell, we got a value 5. It means in s we have a substring of length 5 that is palindrome.