A simple algorithm designed by Manacher in 1975. It scans the longest palindrom in left-to-right fashion.

int palindrom_odd(const char *st, int n, int *p) {

int a = 0, m = 1;

p[0] = 1;

for (int i = 1; i < n; ++i) {

int w = 1;

**if (a + p[a] > i ) **

** w = std::min(p[a + a -i], a-i+p[a]);**

while(i >= w && i+w < n && st[i+w] == st[i-w])

++w;

if (w + i > a + p[a])

a = i;

p[i] = w;

m = std::max (w, m);

}

return m + m – 1;

}

The algorithm is quite straightforward. If you take the two lines in **bold **away, you will immediately see that it becomes a naive palindrom finding algorithm. What are the two lines for?

Assuming you are computing the radius of index and there is some index such that .

*If the palindrom centered at index is covered by the range , then by symetric property, the radius of index cannot be larger than . So it is enough for us to compute starting from .*

Why the algorithm is linear? For each comparison, you either extend the coverage of (on sucess) or finish the computation of immediately.

Is this algorithm fast? Not really, a naive algorithm most probably will beat it in practice. The algorithm is good for interview since it is simple and nature. It is much faster than a naive algorithm in some extreme case (e.g. a lot of 0’s followed by a single 1, in this case, the running time of a naive algorithm is )