Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2014-05-17 15:16:43.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:prefixe.in, prefixe.outSursăONIS 2014, Runda Finala
AutorStefan CiobacaAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Prefixe

După cum ştiţi, lui Gigel îi plac cifrele 0 şi 1. În această problemă, îi place şi cifra 2. El analizează un şir de caractere T format doar din 0, 1 şi 2 şi este fascinat de şabloanele pe care le observă în şir. Caracterul T\[1\] este primul caracter al şirului, T2 al doilea, etc. Şirul are lungime N.

Gigel este interesat de prefixele T1, ..., T[i] ale acestui şir ($1$ ≤ in). El observă că un astfel de prefix de lungime i are la rândul lui anume prefixe care îi sunt şi sufixe. De exemplu, dacă T = 0101012 şi i = 5, în prefixul 01010 se găseşte prefixul 010 care este şi sufix. Vă roagă să gasiţi pentru fiecare prefix T1, ..., T[i] lungimea celui mai mare prefix diferit de T1, ..., T[i] care este şi sufix al T1, ..., T[i].

Date de intrare

Fişierul de intrare prefixe.in conţine pe prima linie numărul T de teste. Urmează T linii, fiecare cu câte un test. Un test constă dintr-un şir format din 0, 1 şi 2.

Date de ieşire

În fişierul de ieşire prefixe.out afişaţi pentru fiecare prefix T1, ..., T[i] al şirului dat la intrare cel mai mare prefix diferit de T1, ..., T[i] care este şi sufix pentru T1, ..., T[i].

Restricţii

  • 1 ≤ n ≤ 131072
  • 1 ≤ T ≤ 128

Exemplu

prefixe.inprefixe.out
1
010010010010
0 0 1 1 2 3 4 5 6 7 8 9

Explicaţie

Pentru T1...T5, prefixul T1,T2 este egal cu sufixul T4,5.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?