Hledání palindromů

Dobrý den programátoři, mám takový problém v Javě (se kterým nemůžu hnout). Studuji na FELu (1. ročník STM) a dostal jsem za úkol vymyslet program, který v proudu znaků najde nejdelší (a nejdelší opakující se) palindrom. Znaky se načítají ze souboru do Stringu (myslím, že je to nejlepší). Problém je ale složitost algoritmu - prohledávání by mělo pro 1 mil. znaků trvat do 1 min, ale mě to neskončí ani po 10 min. :( Pokud máte nějaký nápad, budu rád za každou radu (můžu poslat i zdrojový kód). Předem všem děkuji a přeju hezký den. ;)

Na longest repeated substring je šikovný suffix tree. Stejně tak na longest common substring.
Nechce se mi vymýšlet triky konktréně pro tvoji úlohu, ale nejjednodušší řešení je ten řetězec obrátit (tedy budeš mít dva) a při hledání "longest common substringu" najdeš ten nejdelší palindrom.

---------- Post added 13.1.2012 at 20:14 ----------

Ježiš, to jsem plácnul úplnou blbost... To se tak trochu možná týkalo jen toho "nejdelší opakující se", jinak bych to hledal tak, že v každém místě řetězce, tedy pro 1....n ty znak bych provedl toto:
* podíval bych se, jakou délku ma zatím nejdelší nalezeny palindrom, a zkontroloval, jestli tento znak je středem palindromu min. o jedna delšího (a pokud ano, tak jaké délky maximálně najdu kolem tohoto písmene palindrom)

sice to má složitost n^2, ale typicky to bude mnohem rychlejší (průměrně bych tipoval n*log(n)); například mě napadá kontrolovat palindromovitost od krajů, a ne od středu (což by empiricky mělo skončit neúspěchem v méně krocích, pokud to palindrom není)

a dále je potřeba ošetřit takové věci jako palindrom sudé délky - asi nejjednodušeji že ten krok provádět i mezi znaky, tedy mezi 1 a 2 atd....