sirinf

Sirinf

== include(page="template/taskheader" task_id="sirinf") ==

Poveste şi cerinţă...

Precizare: In timpul concursului testele erau slabe. Acum testele au fost actualizate.
 
Cristinel a gasit un sir de caractere *S* de lungime *N*. Alexei este invidios pentru ca vrea si el un sir de caractere. Din aceasta cauza ei au hotarat ca cine rezolva aceasta problema acela primeste sirul de caractere.
 
Definim stringul infinit *T* ca fiind o concatenare infinita a lui *S*. Cu alte cuvinte, $T = S + S + ... + S$ de un numar infinit de ori. Si Alexei si Cristinel au observat ca stringul *T* are cel mult *N* suffixe distincte. Al *N+1*-lea suffix o sa fie egal cu primul suffix. Al *N+2*-lea suffix o sa fie egal cu al doilea suffix. Si tot asa mai departe. Luam cele *N* suffixe, le sortam lexicografic (in caz de egalitate, dupa indexul suffixului. Pentru a primi sirul de caractere, Alexei si Cristinel trebuie sa raspunda la intrebarea: Pe ce pozitie se afla stringul *S* in lista sortata a celor *N* suffixe?
Mai multe detalii in explicatia exemplului.

h2. Date de intrare

Fişierul de intrare $sirinf.in$ ...

Fişierul de intrare $sirinf.in$ pe prima linie se aflat *T*, numarul de teste intr-un fisier. Apoi, pe urmatoarele linii apare cate un string format din alfabetul limbei engleze.

h2. Date de ieşire

În fişierul de ieşire $sirinf.out$ ...

În fişierul de ieşire $sirinf.out$ se afiseaza *T* linii, pe linia $i$ se afla pozitia stringului *S* in lista sortata a celor *N* suffixe a stringului *T*.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 10^6^$
* $1 ≤ T ≤ 10$

h2. Exemplu
table(example). |_. sirinf.in |_. sirinf.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 5
  cabcab
  mama
  alexei
  cristinel
  dusmaniitraiescprintrenoi
 
| 5
  3
  1
  1
  4
|

h3. Explicaţie

...

$S = cabcab$, $T{~i~}$ reprezinta ai $i$-lea suffix al stringului *T*
suffixele in ordine sortata:
$1) T{~2~} = abcabcabca...$
$2) T{~5~} = abcabcabca...$
$3) T{~3~} = bcabcabcab...$
$4) T{~6~} = bcabcabcab...$
$5) T{~1~} = cabcabcabc...$
$6) T{~4~} = cabcabcabc...$
observam ca stringul initial se afla pe pozitia 5.

== include(page="template/taskfooter" task_id="sirinf") ==