== include(page="template/taskheader" task_id="enigma") ==
Poveste şi cerinţă...
Green şi Riemann sunt doi prieteni buni cărora le place să joace un joc numit “enigma”. În acest joc, unul dintre ei scrie un cuvânt format din $N$ caractere, iar celalalt vine cu $M$ cuvinte de maxim $S$ caractere. Scopul celui de-al doilea jucător este să îşi dea seama în câte moduri poate primul cuvânt să fie format din concatenarea prefixelor unor cuvinte dintre cele $M$.
Dacă s-a găsit un mod de a forma primul cuvânt, atunci fiecare poziţie $i$ a acestuia va avea asociată o pereche $(x, y)$, semnificând faptul că poziţia $i$ este acoperită de al $y$-lea caracter din cuvântul $x$. Astfel, două moduri de a forma primul cuvânt sunt considerate diferite dacă există două poziţii $i$ şi $j$, cu perechile asociate $(x1, y1)$ şi $(x2, y2)$ astfel încât $x1$ $!=$ $x2$ sau $y1$ $!=$ $y2$ .
Realizaţi un program care să rezolve jocul “enigma”!
h2. Date de intrare
Fişierul de intrare $enigma.in$ ...
Fişierul de intrare $enigma.in$ va conţine pe prima linie două numere $N$ şi $M$ cu semnificaţia din enunţ. A doua linie va conţine primul cuvânt format din $N$ caractere. Urmează $M$ linii, fiecare conţinând un cuvânt de maxim $S$ caractere.
h2. Date de ieşire
În fişierul de ieşire $enigma.out$ ...
Fişierul de ieşire enigma.out va conţine pe prima linie numărul de moduri în care primul cuvant poate fi obţinut din concatenarea prefixelor unor cuvinte dintre cele $M$, modulo $31333$ .
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 300 000$
* $1 ≤ M ≤ 4 500$
* $1 ≤ S ≤ 100$
* un caracter este definit ca fiind o literă mică din alfabetul englez
* un cuvânt poate apărea de mai multe ori
* prefixele cuvintelor pot fi doar concatenate, nu şi suprapuse
h2. Exemplu
table(example). |_. enigma.in |_. enigma.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|7 3
xxxabdc
xxx
abdc
c
|8
|
h3. Explicaţie
...
Considerând numerotarea cuvintelor cea din fişierul de intare, perechile asociate poziţiilor primului cuvânt sunt:
$1. (1, 1) (1, 1) (1, 1) (2, 1) (2, 2) (2, 3) (2, 4);$
$2. (1, 1) (1, 2) (1, 1) (2, 1) (2, 2) (2, 3) (2, 4);$
$3. (1, 1) (1, 1) (1, 2) (2, 1) (2, 2) (2, 3) (2, 4);$
$4. (1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (2, 4);$
$5. (1, 1) (1, 1) (1, 1) (2, 1) (2, 2) (2, 3) (3, 1);$
$6. (1, 1) (1, 2) (1, 1) (2, 1) (2, 2) (2, 3) (3, 1);$
$7. (1, 1) (1, 1) (1, 2) (2, 1) (2, 2) (2, 3) (3, 1);$
$8. (1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (3, 1);$
== include(page="template/taskfooter" task_id="enigma") ==
