Manacher's algorithm

Longest palindromic substring is the problem of finding a maximum-length substring of a given string that is also a palindrome. Usually this can be done by dynamic programming or suffix array. However, Manacher's algorithm is a more efficient algorithm that takes only O(n) time.

The main idea is to turn odd/even palindromic substring into odd palindromic string. We add special characters among original characters. For example, we convert 'abba' to '#a#b#b#a#', 'aba' to '#a#b#a#'. And add '$' at the front of the string for handling edge cases.

Let's assume S = '1221' as to illustrate our algorithm. S' = '$#1#2#2#1#'. And we let array P to store the extension to the left(or right) in S'. So here,

S  #  1  #  2  #  2  #  1  #

P  1  2  1  2  5  2  1  2  1

P.S. P[i] - 1 is the length of the original palindrome.

Next question is how to calculate array P. Let id be the max palindromic substring's center, and mx = id + P[id], i.e., the right end of the substring. Then we have the following property:

    If mx > i, the P[i] >= min(P[2 * id - i], mx - i)

int mancher(){
    int mx = 0, id, i, ans = 0;
    memset(p, 0, sizeof(p));

    for (i = 1; i < m; i++){
        if (mx > i){
            p[i] = min(p[2 * id - i], mx - i);
        } else {
            p[i] = 1;
        }
        for ( ; str2[i - p[i]] == str2[i + p[i]]; p[i]++);
        if (i + p[i] > mx){
            mx = i + p[i];
            id = i;
        }
    }
    for (i = 0; i < m; i++){
        ans = max(ans, p[i]);
    }
    ans--;
    return ans;
}