I recently read a wikipedia article on Manacher's algorithm and after seeing the sample implementation and dozens of other implementations... I'll be honest I have no clue how this algorithm is linear. The way I see it, it's rather in the best case O(n+n/2) but that's not linear, is it?
http://en.wikipedia.org/wiki/Longest_palindromic_substring
For each character within the original string we're trying to expand the P array in both directions until we either reach a string boundary or the symmetrical property is not satisfied. If it would only be like so this'd mean O(n^2) but with the extra observations will be less than that. Still at most I could get my head down to O(n+n/2) but not to O(n) as that would esentially mean the internal nested loop o(1). Anything higher than that and it's higher breaks the linearity for the whole algorithm.
so in a nutshell, how is this algorithm linear?
O(n + n/2) is linear, O(n+n/2) ~ O(n)
The time is still proportional to n.
Or, being more precice, the limit of (n+n/2) / n as n goes to infinity (and also when it doesn't) is a finite constant. So O(n+n/2) and O(n) are equivalent.