Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | codificare.in, codificare.out | Sursă | Tabăra ICHB 2012, Ziua 1, Grupa 1 |
| Autor | Dan Constantin Spatarel | Adăugată de |  Dan-Constantin Spatarel •spatarel |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 5120 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Codificare
În ultima misiune în care a participat, Birkoff a trebuit să spargă sistemul de telecomunicaţii radio al infractorilor - ceva banal pentru el, desigur. Acum, că misiunea s-a terminat cu succes, Birkoff ştie codul de criptare folosit de inamici şi îl studiază, pentru a-şi putea scrie raportul misiunii.
Codul de criptare este un şir C de lungime N format din caractere mici ale alfabetului englez. Birkoff se întreabă în câte moduri se poate obţine şirul C pornind de la un subşir S al său de lungime 1, folosind succesiv următoarele operaţii:
- prefixează şirul S cu un caracter;
- sufixează şirul S cu un caracter.
În timp ce voi citeaţi problema, Birkoff s-a apucat deja să-şi scrie raportul. Dacă vreţi să ajungeţi şi voi într-o bună zi ca el, va trebui să răspundeţi la întrebarea sa pentru orice subşir S.
Date de intrare
Fişierul de intrare codificare.in conţine pe prima linie numărul natural N şi pe a doua linie şirul de caractere C.
Date de ieşire
În fişierul de ieşire codificare.out se va găsi pe prima linie numărul natural K reprezentând numărul de subşiruri distincte de lungime 1 ale şirului C.
Pe fiecare din următoarele K linii se vor regăsi, separate printr-un spaţiu, un subşir S şi numărul de moduri de a ajunge de la acesta la şirul C modulo 666013. Cele K linii vor fi sortate lexicografic.
Restricţii
- 1 ≤ N ≤ 100 000
Exemplu
| codificare.in | codificare.out |
|---|---|
| 3 aba | 2 a 2 b 2 |
Explicaţie
Subşirurile distincte S sunt a şi b. Pentru fiecare există câte două modalităţi prin care se poate obţine şirul C:
- a -> ab -> aba
- a -> ba -> aba
- b -> ba -> aba
- b -> ab -> aba
