Ti hogyan fognátok neki a probléma megoldásának?

nem triviális...

bekéred az 1000 karaktert. Aztán egyesélvel végigmész a listán, ami ad egy ezer hosszúságú tömböt. Ha van azonos akkor nyeremény.

Aztán kettessével mész végig a tömbön

Aztán hármasával stb stb stb

Egészen 998-asával, mert akkor 0-tól 998-ig egy lánc, 1-től 999-ig pedig egy második.

Amelyik listában utoljára van nyeremény, azt kell majd kiíratnod.

Így belegondolva fordítva egyszerűbb. A hosszabb listáktól menj a rövidebb felé.

Eloszor egy egyszeru megoldast gondoltam at:

ciklus i megy 1tol n-1ig

ciklus j megy i+1tol n-ig

_ ciklus reszlethossz megy 0-tol n/2-ig, es amig szoveg[i+reszlethossz]=szoveg[j+reszlethossz]

_ maxreszlethossz = max(maxreszlethossz, reszlethossz)

Aztan arra gondoltam hogy valaki ezt nyilvan megoldotta gyorsabban mint O(n^2).

Ugyhogy rakerestem:

[link]

Az én megközelítésem egy picit más lenne.

Az alapkoncepció, hogy ha mondjuk van egy n karakter hosszú sorozat, ami kétszer szerepel, akkor annak a sorozatnak minden részsorozata is szerepel kétszer. Tehát akkor n-1, n-2, n-3, stb, stb hosszú részsorozatai is kétszer szerepelnek, ebből következik, hogy az első karaktere is egyezik. Tehát neked anynia dolgod, hogy egyetlen karakterrel találj egyezést, és után attól a két első karaktertől lépkedsz előre, amíg tovább egyeznek a karakterek. Ha neme gyeznek, akkor összeveted a jelenelgi elghosszabb eltárolt stringgel, hogy hosszabb-e nála. Sőt, ha mondjuk n karakter hosszú az aktuálisan ismert leghosszabb string, akkor megnézheted egy karakteregyezésnél rögtön azt, hogy n karakterrel előrébb is egyeznek-e. Ha nem, akkor fölösleges tovább építeni, mert úgysem fogja elérni az előző hosszúságát, keresheted a következő első karakteres egyezést. Így a program lényegi műveletigénye ezeknek az első karakteres egyezésekből épül fel. Erre az egyszerű metodika az, hogy először az első karaktert hasonlítod össze az utána következőkkel, aztán a második karaktert az azután következőkkel, és így tovább, egészen addig, amíg közelebb kerülsz a string végéhez, mint az aktuális leghosszabb találat. Mivel elég mindig csak a soron következő szám után következő karaktereket nézni, így a ciklusod minden körben egyre rövidebb lesz, összességében egy O(n^2) műveletigényű algoritmust kapunk. Lehetne rajta gyorsítani, de alapvetően ez se rossz.