Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2014-05-17 15:17:00.
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 T1 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?