Time limit: 0.85s
Memory limit: 256MB
Input: textmare.in
Output: textmare.out
Se dă un șir de caractere alcătuit din N
litere mici din alfabetul latin, ce reprezinta o frază; între cuvinte nu apar spații de separare. De asemenea se dă un vocabular, format din M
cuvinte care nu sunt neapărat diferite și nu apar într-o ordine prestabilită.
Cerință
Despărțiți fraza într-un număr minim de cuvinte; toate aceste cuvinte trebuie să existe în vocabularul dat.
Date de intrare
Fișier de intrare: textmare.in
- pe prima linie apare fraza care trebuie despărțită în cuvinte;
- următoarea linie conține numărul de cuvinte din vocabular;
- următoarele linii conțin câte un cuvânt din vocabular;
Date de ieșire
Fișier de ieșire: textmare.out
Fișierul este format din fraza despărțită în cuvinte. Între oricare două cuvinte consecutive va apărea exact câte un blanc. Fișierul se va termina cu o linie goală. Dacă nu există soluție, în fisierul de ieșire se va scrie doar cifra 0
;
Restricții și precizări:
- Fie
S
numărul total de caractere din dicționar. - Pentru
25
de puncte:1 ≤ N, M ≤ 1 000
și fiecare cuvânt din vocabular are cel mult16
caractere. - Pentru încă
35
de puncte:1 ≤ N, M ≤ 32 000
și fiecare cuvânt din vocabular are cel mult16
caractere. - Pentru încă
40
de puncte:1 ≤ N ≤ 100 000, 1 ≤ M ≤ 500 000, 1 ≤ S ≤ 500 000
. - Dacă există mai multe soluții, la ieșire va fi produsă una singură;
- Într-o frază un singur cuvânt din vocabular poate să apară de mai multe ori.
Exemplu
textmare.in
acestaesteuntext
8
text
acesta
acest
a
care
este
un
simplu
textmare.out
acesta este un text