## Simple linear palindrom finding algorithm

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 $i$ and there is some index $a < i$ such that $p[a] + a > i$.
If the palindrom centered at index $2a-i$ is covered by the range $[a-p[a], a+p[a]]$, then by symetric property, the radius of index $i$ cannot be larger than $p[2a-i]$. So it is enough for us to compute $p[i]$ starting from $min(p[a + a -i], a-i+p[a])$.
Why the algorithm is linear? For each comparison, you either extend the coverage of $a+p[a]$ (on sucess) or finish the computation of $p[i]$ 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 $\Theta(n^2)$)