textmare

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 mult 16 caractere.
  • Pentru încă 35 de puncte: 1 ≤ N, M ≤ 32 000 și fiecare cuvânt din vocabular are cel mult 16 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

Log in or sign up to be able to send submissions!