|
Titlul: 2648. Archiver Scris de: Cosmin Rusu din Octombrie 17, 2014, 22:31:26 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) ? Titlul: Răspuns: 2648. Archiver Scris de: George Marcus din Octombrie 22, 2014, 18:59:57 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 = Y1Y2, Z = Z1Z2, Y1 = Z1, Y2 = Z2 si Z2 este prefix al lui [m+1,dr]. [ ... Y1 Y2 Z1 ] [ Z2 ... ] st m m+1 dr Incercam toate pozitiile de inceput i pentru Y2. Y2 se poate termina cel tarziu la min(i + Z[i] - 1, m - 2). Deci avem un interval de posibilitati pentru Y2. Incercam sa determinam un astfel de interval si pentru Z1. Z1 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 Y2 incepe la i). La 1c) luam intervalele invers si se reduce la 1b). Deci complexitatea e O(NlogN). Sursa mea: http://ideone.com/vC4bJT |