2648. Archiver

[•CosminRusu]

http://www.spoj.com/problems/KPARCH/

Imi dati si mie o idee cum as putea folosi Suffix Arrays in problema asta? La comentarii se mentioneaza si despre 'extended KMP', oare la ce se refera (pe google nu am gasit nimic despre asa ceva) ?

[•PlayLikeNeverB4]

Am gasit pe net o solutie cu Divide et Impera + Z-algorithm. Ideea e asa:

Tu cauti toate substringurile X = YZ, unde Y si Z sunt stringuri nevide si Y = Z.

Cauti toate substringurile de aceasta forma din intervalul [st, dr]. Fie m mijlocul intervalului.
Ai 3 cazuri:
1) X incepe in prima jumatate ([st,m]) si se termina in a doua jumatate ([m+1,dr]).
2) X se afla in intregime in prima jumatate
3) X se afla in intregime in a doua jumatate

Pentru cazurile 2) si 3) mergi recursiv si afli raspunsul pentru intervalele respective.

Ramane cazul 1). Ai 3 subcazuri:
1a) Y se termina exact la m
1b) Y se termina inainte de m
1c) Y se termina dupa m

Cu ajutorul algoritmului Z calculam vectorul Z, Z[i] = cel mai lung prefix al lui [m+1,dr] astfel incat acesta sa fie prefix si pentru [i,m].

Stringurile de la 1a) sunt acele stringuri care respecta proprietatea ca incep la i si i + Z[i] - 1 = m.

Pentru 1b) mai trebuie sa calculam vectorul RZ, RZ[i] = cel mai lung sufix al lui [st,m] astfel incat acesta sa fie sufix si pentru [st,i] (practic algoritmul Z pe sirul inversat).

Impartim stringurile Y is Z in doua parti astfel incat Y = Y₁Y₂, Z = Z₁Z₂, Y₁ = Z₁, Y₂ = Z₂ si Z₂ este prefix al lui [m+1,dr].

[ ... Y₁ Y₂ Z₁ ]   [ Z₂ ... ]
st               m m+1     dr

Incercam toate pozitiile de inceput i pentru Y₂. Y₂ se poate termina cel tarziu la min(i + Z[i] - 1, m - 2). Deci avem un interval de posibilitati pentru Y₂. Incercam sa determinam un astfel de interval si pentru Z₁. Z₁ poate incepe cel mult la max(i + 1, m - RZ[i - 1]). Avand aceste doua intervale, putem calcula cate stringuri intra in acest caz (cand Y₂ incepe la i).

La 1c) luam intervalele invers si se reduce la 1b).

Deci complexitatea e O(NlogN).

Sursa mea: http://ideone.com/vC4bJT