>215
ググったらこれO(n)でできるらしい。
古典的な問題として有名らしい。
http://www.prefield.com/algorithm/string/manacher.html
にあった。

よくこんな事思い付くよな。