== include(page="template/taskheader" task_id="em2") ==
Poveste și cerință...
_Notă: acesta este un exercițiu introductiv de lucru cu matrice._
Se citește o matrice pătrată *A* de caractere litere mici, precum și un șir *S* de litere mici.
h2. Cerință
# Să se spună de cîte ori apare șirul *S* în matricea *A* pe linii, de la stînga la dreapta.
# Să se afișeze pe o singură linie unele din caracterele matricei *A* astfel:
** Mai întîi acele diagonale paralele cu diagonala secundară care pornesc de pe diagonala principală.
** Apoi diagonalele aflate deasupra diagonalei secundare, parcurse de la la dreapta la stînga.
h2. Date de intrare
Fișierul de intrare $em2.in$ ...
Fișierul de intrare $em2.in$ *n*+1 linii de litere mici terminate cu sfîrșit de linie. Primele *n* linii au același număr *n* de litere, ele descriind matricea *A*. Linia *n*+1 are *m* caractere, ea conținînd șirul *S*.
h2. Date de ieșire
În fișierul de ieșire $em2.out$ ...
În fișierul de ieșire $em2.out$ se vor afișa două linii:
* Pe prima linie veți afișa numărul de apariții ale șirului *S* în matricea *A*, pe linii, de la stînga la dreapta.
* Pe a doua linie veți afișa caracterele cerute din matricea *A*.
h2. Restricții
* $... ≤ ... ≤ ...$
* 1 ≤ *n* ≤ 1 000 000
* 1 ≤ *m* ≤ 350 000
* *m* ≤ *n*
* Caracterele din matricea *A* și din șirul *S* sînt litere mici
* Ultima linie la intrare conține caracterul de final de linie, *\n*
* Pentru rezolvarea primei cerințe se acordă 20% din punctaj, pentru rezolvarea celei de-a doua cerințe se acordă 80% din punctaj
h2. Exemplu
table(example).
|_. em2.in |_. em2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
|_. em2.in |_. em2.out |_. explicație |
| abcd
efgh
ijkl
mnop
gko
| 1
aebifcmjogld
| Șirul _gko_ apare o singură dată în matrice, pe coloane, de sus în jos.
Diagonalele aflate deasupra diagonalei secundare sînt: _a_ _eb_ _ifk_.
Diagonalele paralele cu cea principală, care pornesc din diagonala secundară, sînt:
_m_ _jo_ _gl_ _d_.
Alipind aceste șiruri obținem răspunsul la a doua cerință.
|
| bcbba
abaab
aabba
baaab
baaaa
aba
| 4
bacabbbaabbaabaaaaa
| Șirul _aba_ apare de patru ori în matrice:
- pe linia a doua, la a treia și a patra coloană
- pe coloana a cincea, la prima și a treia linie
Diagonalele aflate deasupra diagonalei secundare sînt: _b_ _ac_ _abb_ _baab_.
Diagonalele paralele cu cea principală, care pornesc din diagonala secundară, sînt:
_b_ _aa_ _baa_ _aa_ _a_.
Alipind aceste șiruri obținem răspunsul la a doua cerință.
|
== include(page="template/taskfooter" task_id="em2") ==
