Longest Palindrome Substring O(n) Algorithm

Here is a very detailed explanation of the O(n) algorithm: https://www.felix021.com/blog/page.php?pageid=6

The key ideas are :

• We look for the center of the palindrom
• when scan the string we want to use the previous calculation
• palindrome is symmetric and we want to take advantage of this symmetric structure

This algorithm is a combination of Dynamic Program and Pruning. 

Here is the implementation:

int longestPalindromeSubstring(string inStr) {
    
    // insert "space" between charaters in the orignal string.
    // this is a very useful pre-processing; it unifies the odd-length and even-length palindrom substring
    // It is obvious that we should use a character that does not appear in the original string.
    string s;
    for (int i = 0; i < inStr.size(); ++i) {
        s = s + '#';
        s = s + inStr[i];
    }
    s = s + '#';
    
    
    
    vector<int> P(s.size(), 0);
    
    // Here is the definition of the op_center and op_length:
    // op_center + op_length is the right-most boundary of the known palindrome substring.
    
    int op_center = -1;
    int op_length = 0;
    int record = numeric_limits<int>::min();
    
    // now, we scan the string and update op_center and op_length as well as the maximum lenght
    // of the palindrome substring.
    
    for (int i = 0; i < s.size(); ++i) {
        int curr_length = 0;
        if (i <= op_center + op_length) {   // when current position is covered by a known palindrome substring
            int j = 2 * op_center - i;      // here we take advantage of the symmetric structure
            curr_length = P[j];
        }
        
        // perform the two direction search
        while (i + curr_length < s.size() && i - curr_length >= 0 &&
               s[i+curr_length] == s[i-curr_length]) {
            ++curr_length;
        }
        
        P[i] = --curr_length;
        
        // update the record
        record = max(record, curr_length);
        if (i + curr_length > op_center + op_length) {
            op_center = i;
            op_length = curr_length;
        }
        
    }
    
    return record;
}