Sziasztok,
megpróbáltam leprogramozni ezt az algoritmust, de elakadtam, és van
egy kérdésem.
Jól értettem, hogy visszavezettük a problémát egy leghosszabb
ismétlődő részstring keresésére? Például: ha "abcvucbaww"-ben keresünk
leghosszabb részpalindromot, akkor ehelyett "abcvucbaww$wwabcuvcba"
-ban keresünk leghosszabb ismétlődő részstringet? Ezzel az a
problémám, hogy így az eredmény "abc" vagy "cba" lesz a helyes
"zz"
helyett. Szóval valószínűleg rosszul értettem. Konkrétan az nem
világos, hogy mit csinálunk, amikor elkészült a "gyorsítótömbünk".
Viszont, lineáris időben is megoldható a probléma! Ezt állítólag négy
hónapig tartott kitalálni egy PhD hallgatónak, úhgyhogy nem jövőheti
feladatnak ajánlom, hanem belinkelem a megoldást:
http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-i…
Ettől függetlenül szeretném megérteni Máté verzióját is!
Gábor
2009/9/17 Ildi Schlotter <schlotterildi(a)gmail.com>om>:
Sziasztok,
Mate kuldott egy feladatot (koszonjuk!), lehet rajta gondolkodni holnapig:
Adott egy maximum 10^4 hosszu string (mondjuk az
angol abc kisbetuibol).
Keressuk meg a leghosszabb palindrom-reszstringjet.
Ildi
_______________________________________________
acm-valogato mailing list
acm-valogato(a)sziami.cs.bme.hu
http://sziami.cs.bme.hu/mailman/listinfo/acm-valogato