.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » sirag

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
sirag


Timp maxim de execuţie / test:
0.2s
Memorie totala disponibilă / stivă:
16MB / 1MB

În căutarea visului său de preamărire, Lunasorab a dat peste un şirag de perle de lungime N, de diferite tipuri, reprezentate printr-o literă mică a alfabetului latin. Dintre acestea, perlele marcate cu * sunt considerate magice. Ele se pot transforma (şi trebuie transformate) într-o perlă de orice tip nemagic. Acum Lunasorab a primit un număr natural L şi ştie că dacă poate găsi o subsecvenţă de lungime cat mai mare în şiragul iniţial, formată din concatenarea repetată a unei subsecvenţe de lungime L a şiragului cu ea însăşi, o poate vinde pe piaţa neagră contra unei sume considerabile (Lunasorab nu se sfieşte în a folosi metode neconvenţionale pentru a-şi atinge scopurile).
Deoarece Lunasorab nu stă prea bine la capitolul stiinţe exacte (are alte talente), vă cere vouă ajutorul.
De asemenea, fiind mai neîncrezator din fire, Lunasorab vă cere răspunsul pentru mai multe şiraguri.

Cerinţă

Pentru fiecare şirag din fişierul de intrare, aflaţi cea mai lungă subsecvenţă a şiragului, care se poate obţine prin concatenarea unei subsecvenţe de lungime L.

Date de intrare

Fişierul de intrare sirag.in va conţine pe prima linie numărul natural T, reprezentând numărul de teste.
Pe următoarele 2*T linii vor urma cele T teste, formatate după cum urmează: pe prima linie corespunzătoare unui test vor fi numerele naturale N şi L, separate printr-un singur spatiu, reprezentând lungimea şiragului, respectiv lungimea subsecvenţei folosite în repetiţie. Pe a doua linie se vor afla N caractere, reprezentând tipul celor N perle.

Date de ieşire

Fişierul de ieşire sirag.out va avea T linii, fiecare linie continând un număr natural M, ce reprezintă lungimea celei mai lungi subsecvenţe cu proprietatea menţionată pentru testul respectiv.

Restricţii

1 ≤ T ≤ 10
1 ≤ N ≤ 100.000
1 ≤ L ≤ N

Tipurile perlelor vor fi reprezentate ori printr-o literă mică a alfabetului latin, ori prin caracterul * pentru perle magice
Pentru 10% din teste L = 1
Pentru 30% din teste N ≤ 2000

Exemple

sirag.insirag.outExplicaţii
1 6 3 a*cab* 6 Şirul se poate transforma în abcabc, înlocuind prima perlă magică cu b, iar a doua cu c . Atunci secvenţa abc se repetă de 2 ori, si deci se poate obţine o subsecvenţă de lungime 6 (tot şiragul) cu proprietatea menţionată.

autor: Cătălin Tiseanu
propunător: Prof. Emanuela Cerchez
Liceul de Informatica ″Grigore Moisil″
emanuela.cerchez@gmail.com
Articole recomandate
Despre heap: Heap-uri
Probleme recomandate
surse trimise | ajutor