Manacher Algorihtm

To calculate the longest palindrome substring.

Algorihtm

• preprocessing
  insert ‘#’ between adjacent characters in the string, e.g., babad $\rightarrow$ #b#a#b#a#d#.
  remark: after preprocessing, the length of the string after and the length of the palindrome substring is odd.
• array P
  P[i]: The maximum extension length of the palindrome substring centered on the i-th character.
  For example: abbabb
  
• calculate P with previous information.
  maxRight: the rightmost boundray. $${\rm maxRight} = \max\{x + {\rm P}[x]\mid 0\le x < i\}.$$ center: the center correpsonds to maxRight. $${\rm center} = \arg\max\{x + {\rm P}[x] \mid 0 \le x < i\}.$$
  • case 1: $i \ge {\rm maxRight}$
    extend at the i-th character to enlarge maxRight.
  • case 2: $i < {\rm maxRight}$
    find mirror which is symmetric with $i$ about center, i.e., ${\rm mirror} + i = 2\times {\rm center}$.
    • ${\rm P}[{\rm mirror}] < {\rm maxRight} - i$, which means that ${\rm P}[i] = {\rm P}[{\rm mirror}]$.
      
    • ${\rm P}[{\rm mirror}] = {\rm maxRight} - i$, which means that ${]rm P}[i]$ is at least ${\rm maxRight} - i$ and may be extended.
      
    • ${\rm P}[{\rm mirror}] < {\rm maxRight} - i$, which means ${\rm P}[i] = {\rm maxRight} - i$ and can not be extended.
      

In summary, ${\rm P}[i] = \min\{ {\rm maxRight} - i, {\rm P}[{\rm mirror}] \}$.

string manacher(string str) {
    string str_trans = "#";
    for (char c : str) {
        str_trans += c;
        str_trans += '#';
    }
    int n  = str_trans.length();
    vector<int> p(n, 0);
    int maxRight = 0, center = 0;
    int maxLen = 1, start = 0;
    for (int i = 0; i < n; ++ i) {
        if (i < maxRight) {
            int mirror = 2*center - i;
            p[i] = min(maxRight - i, p[mirror]);
        }
        int left = i - (1 + p[i]), right = i + (1 + p[i]);
        while (left >= 0 && right <= n && str_trans[left] == str_trans[right]) {
            p[i] ++;
            left --;
            right ++;
        }
        if (i + p[i] > maxRight) {
            maxRight = i + p[i];
            center = i;
        }
        if (p[i] > maxLen) {
            maxLen = p[i];
            start = (i - maxLen)/2;
        }
    }
    return str.substr(start, maxLen);
}