Manacher's algorithm

Posted on | Edited on | In

O(n) time complexity find longest palindromic substring

Translate

put origin string into a new char array, take “ABBABCBA”
make odd/ even length origin string into a odd length array (#,…,#)

1
char S[] = {'^', '#', 'A', '#', 'B', '#', 'B', '#', 'A', '#', 'B', '#', 'C', '#', 'B', '#', 'A', '#', '\0'};

1
char S[] = {'^', '#', 'A', '#', 'B', '#', 'B', '#', 'A', '#', 'B', '#', 'C', '#', 'B', '#', 'A', '#', '$'};

put position 0 and last postion a placeholder, S.length = origin * 2 + 3 odd length.

Mark

declare a array P[] to mark the S’s char symmetric radius length

1
2
char S[] = {'^', '#', 'A', '#', 'B', '#', 'B', '#', 'A', '#', 'B', '#', 'C', '#', 'B', '#', 'A', '#', '$'};
int  P[] = { 0 ,  1 ,  2 ,  1 ,  2 ,  5 ,  2 ,  1 ,  4 ,  1 ,  2 ,  1 ,  6 ,  1 ,  2 ,  1 ,  2 ,  1 ,  0 };

describe:

array P used to describe radius, for example :

P[5] = 5 -> S(1,5) | S(5, 9)

calculate:

Declare varable

  1. center the center of mirror
  2. right the right terminal of mirror

right = center + P[center] , right point = center point + radius

left = center - P[center] , left point = center point - radius

declare i as current S cursor

delcare mirror as the i’s mirror index ps. 2*center - right

when right > i, then P[i] >= Min(P[mirror], right - i)

  1. when P[mirror] is minimum, that meaning P[mirror] < right - i

    standard check block: (mirror - P[mirror], mirror + P[mirror]) | (i-P[mirror], i + P[mirror])
  2. when right - i is minimum, that meaning P[mirror] > right - i

    mirror - P[mirror] across the circle left border.

    standard check block: (mirror - (right - i), mirrror + (right - i)) | (i - (right - i), right)

Code & Graph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// right = center + P[center]
int center = 0, right = 0;
// exclude last placeholder position
for (int i=1; i<S.length-1; i++) {
    // j = 2*center - i
    P[i] = right > i? Math.min(P[2*center - i], right - i): 1;

    // include char itself, 1 bigger than standard implements
    while(S[i + P[i]] == S[i - P[i]]) P[i]++;

    // judge whether new radiu cross border
    if(i + P[i] > right) {
        right = i + P[i];
        center = i;
    }

}

Biggest value in P[] is longest palindromic substring lengh
It’s index is substring’s char center index.

1
2
3
4
5
// find biggest value in P[]
length--;
// and it's index
center--;
src.substring((center - length) / 2, (center + length) / 2)

thanks:
https://www.felix021.com/blog/read.php?2040