Diferente pentru problema/prefixe intre reviziile #5 si #25

Diferente intre titluri:

prefixe
Prefixe

Diferente intre continut:

== include(page="template/taskheader" task_id="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, $T[2]$ al doilea, etc. Şirul are lungime $N$.
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, $T{~2~}$ al doilea, etc. Şirul are lungime $N$.
Gigel este interesat de prefixele $T[@1@], ..., T[i]$ ale acestui şir ($1$ ≤ $i$ ≤ $n$). 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 $T[1], ..., T[i]$ lungimea celui mai mare prefix diferit de $T[1], ..., T[i]$ care este şi sufix al $T[1], ..., T[i]$.
Gigel este interesat de prefixele $T{~1~}, ..., T{~i~}$ ale acestui şir ({$1 ≤ i ≤ N$}). 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 $T{~1~}, ..., T{~i~}$ lungimea celui mai mare prefix diferit de $T{~1~}, ..., T{~i~}$ care este şi sufix al $T{~1~}, ..., T{~i~}$.
h2. 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$.
Fişierul de intrare $prefixe.in$ conţine pe prima linie numărul $Z$ de teste. Urmează $Z$ linii, fiecare cu câte un test. Un test constă dintr-un şir format din $0$, $1$ şi $2$.
h2. Date de ieşire
În fişierul de ieşire $prefixe.out$ afişaţi pentru fiecare prefix $T[1], ..., T[i]$ al şirului dat la intrare cel mai mare prefix diferit de $T[1], ..., T[i]$ care este şi sufix pentru $T[1], ..., T[i]$.
În fişierul de ieşire $prefixe.out$ afişaţi pentru fiecare prefix $T{~1~}, ..., T{~i~}$ al şirului dat la intrare lungimea celui mai mare prefix diferit de $T{~1~}, ..., T{~i~}$ care este şi sufix pentru $T{~1~}, ..., T{~i~}$. Lungimile trebuie separate prin spaţii.
h2. Restricţii
* $1 ≤ n ≤ 131072$
* $1 ≤ T ≤ 128$
* $1 ≤ N ≤ 131072$
* $1 ≤ Z ≤ 128$
h2. Exemplu
h3. Explicaţie
Pentru $T[1]...T[5]$, prefixul $T[1],T[2]$ este egal cu sufixul $T[4],[5]$.
Pentru $T{~1~}...T{~5~}$, prefixul $T{~1~},T{~2~}$ este egal cu sufixul $T{~4~},{~5~}$, deci al $5$-lea număr de la ieşire este $2$, lungimea şirului $T{~1~},T{~2~}$.
== include(page="template/taskfooter" task_id="prefixe") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
9906