9-line KMP approach C++. Can it be regarded as Dynamic Programming???


  • 0
    W

    Here I present my 9-line KMP approach in C++. First, let me share my thoughts on this problem:

    1. It is easy to see that in order to find the shortest concatenated palindromic string, we need to find the longest palindromic prefix of the original string, namely a substring str[0...k] starting at 0 index.
    2. In order to find the longest palindromic prefix, we can use brute-force approach. The idea is a middle-out approach. For i from (s.size()-1)/2 to 0, we find the longest palindromic prefix centered at s[i]. Here the trick is that we need to consider prefix with odd length and with even length. We use a subroutine check() to check whether the palindrome starts at 0 index. Here is the code:
    public:
        string shortestPalindrome(string s) {
            string rt = s + s;
            int size = s.size();
            if(s.empty()) return s;
            bool found = false;
            for(int i = (size-1)/2; i >= 0; i--) {
                int l = i, r = i+1;
                if(check(rt, s, l, r)) break;
                l = i-1, r = i+1;
                if(check(rt, s, l, r)) break;
                
            }
            return rt;
        }
        
    private:
        bool check(string& rt, string& s, int l, int r) {
            int size = s.size();
            while(l >= 0 && r < size && s[l] == s[r]) {
                l--;
                r++;
            }
            if(l == -1 && rt.size() > size + size-r) {
                string temp = s.substr(r);
                reverse(temp.begin(), temp.end());
                rt = temp + s;
                return true;
            }
            return false;
        }
    
    1. Although this code is accepted, it takes 700+ ms, and the time complexity is O(n^2), of course. Can we find the longest palindromic prefix in O(n) time? After read the discussion, I know that the KMP algorithm can do that. Specifically, we can use the subroutine that creates the so-called "partial matching table" T. T[i] means the length of longest equal suffix and prefix in substring str[0...i]. If we concatenate the original string with its reverse string (new string is referred to as conStr), when we find a longest equal suffix and prefix in conStr, that prefix is exactly the longest palindromic prefix of the original string. Now, the approach is clear:
      (a) Create a new string conStr = s + '&' + revStr, where s is the original string, revStr is the reverse of s, and & is a character that never appears in s, in order to make sure the palindromic prefix shorter than s.
      (b) Create partial matching table for conStr using the subroutine of KMP algorithm.
      (c) Append the front part of revStr to the beginning of s. The appended string is the answer. As we can see, the code is elegant and clear.
    string shortestPalindrome(string s) {
            string revstr = s;
            reverse(revstr.begin(), revstr.end());
            string temp = s + '&' + revstr;
            vector<int> table(temp.size(), 0);
            for(int i = 1, j = 0; i < temp.size(); i++) {
                while(j > 0 && temp[j] != temp[i]) j = table[j-1];
                if(temp[j] == temp[i]) table[i] = ++j;
            }
            return revstr.substr(0, revstr.size()-table.back()) + s;
        }
    

    Now, let me share some thoughts on the creation of partial matching table T. As mentioned above, T[i] means the length of longest equal prefix and suffix in substring str[0...i]. For example, if T[i] = 3, then str[0..2] = str[i-2..i]. To fill in this table, we need to maintain two pointers, i and j. i points to the last character of suffix, and j points to the last character of prefix. If str[i] == str[j], we can increase the length of equal prefix and suffix by 1. If str[i] != str[j] we need to retrieve the correct index for j such that we can continue compare str[i] and str[j]. If you don't understand, does not matter. Let's see an example, for str = "ababbababa":
    id : 0 1 2 3 4 5 6 7 8 9
    str: a b a b b a b a b a
    T[i] 0 0 1 2 0 1 2 3 4 3
    Note that, when i = 8, j should point to 3, and str[3] == str[8], so T[8] = j+1 = 4, which means the length of longest equal suffix and prefix in str[0...8] is 4, because str[0..3] == str[5..8]. Now i comes to 9 and j comes to 4, we find that str[4] != str[9], so what is the length of longest suffix and prefix in str[0...9]? We can easily see that since str[0..2] == str[7..9], so T[9] should be 3. However, do we need to search from the beginning? No! KMP algorithm told us we can utilize the information of subproblem in T. j should retreat to T[j-1], until either j == 0 or str[j] == str[i]. So in this example, since str[9] mismatches str[4], j is retreated to T[j-1] = T[3] = 2, now str[2] == str[9], so T[9] is 3. To capture this logic, I (personally) regard it as a dynamic programming paradigm.

    T[i] = ++j, where str[i] == str[j] <-- while(j > 0 && str[j] != str[i]) j = T[j-1];
    

    Let see another example:
    id : 0 1 2 3 4 5 6 7 8 9
    str: a b a b b a b a b x
    T[i] 0 0 1 2 0 1 2 3 4 0
    When i = 9 and j = 4, we compare str[9] and str[4], mismatch, j = T[j-1] = 2, str[2] != str[9], mismatch, j = T[j-1] = 0, mismatch, but j == 0, so T[9] = T[9] = 0;


  • 0
    C

    What is the time complexity of constructing the partial matching table?Is that O(N)?


  • 0
    W

    @chaos28 Yes, it is O(N). You may refer to KMP method.


Log in to reply
 

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