Fişierul intrare/ieşire:sablon.in, sablon.outSursăONI 2015, clasa a 10-a
AutorRadu VisinescuAdăugată deharababurelPuscas Sergiu harababurel
Timp execuţie pe test0.35 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sablon

Se consideră alfabetul englez compus din literele mici, de la a la z.
Se numeşte cuvânt un şir finit, eventual vid, de litere din acest alfabet.
Se numeşte expresie şablon un şir de caractere din alfabet în care pot apărea şi caracterele ? şi *.
Un cuvânt se potriveşte cu o expresie şablon dacă se poate obţine din aceasta astfel:

  • caracterul ? se înlocuieşte cu o singură literă din alfabet;
  • caracterul * se înlocuieşte cu un cuvânt oarecare, eventual vid;
  • din expresia şablon se poate elimina sau nu, înainte de a efectua înlocuirea caracterelor ? şi *, un singur caracter de tip literă.

Cerinţă

Considerându-se o expresie şablon şi un şir de cuvinte, să se determine, pentru fiecare cuvânt în parte, dacă se potriveşte sau nu cu expresia şablon dată.

Date de intrare

Fişierul de intrare sablon.in conţine:
Pe prima linie se găseşte o expresie şablon E.
Pe a doua linie se găseşte un număr natural N, ce reprezintă numărul de cuvinte din şir.
Pe fiecare din următoarele N linii se găseşte câte un cuvânt S_{i}, (1 \leq i \leq N).

Date de ieşire

Fişierul de ieşire sablon.out va conţine pe fiecare din primele N linii valoarea 1 sau 0, după cum cuvântul S_{i}, (1 \leq i \leq N) se potriveşte cu expresia şablon E.

Restricţii

  • 1 ≤ N ≤ 10
  • Pentru 16\% din teste expresia şablon E nu conţine caracterul * iar lungimea lui E şi a oricărui cuvânt S este între 1 şi 1000 de caractere.
  • Pentru alte 16\% din teste lungimile lui E şi S sunt cuprinse între 1 şi 20 de caractere.
  • Pentru alte 32\% din teste lungimile lui E şi S sunt cuprinse între 1 şi 100 de caractere.
  • Pentru restul de 36\% din teste lungimile lui E şi S sunt cuprinse între 1 şi 1500 de caractere.

Exemplu

sablon.insablon.out
a*a?b
7
ababb
aab
aabb
bac
abcaab
abcaab
ababa
1
1
1
0
1
1
0

Explicaţie

  • Cuvintele ababb, aabb şi abcaab se potrivesc cu expresia şablon.
  • Cuvântul aab se potriveşte cu expresia şablon obţinută prin eliminarea în prealabil a unuia din caracterele a.
  • Cuvintele bac şi ababa nu se pot obţine în nicio situaţie din expresia şablon.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?