Rezolvare completă PbInfo #1493 Masca

Se consideră alfabetul compus din literele mici, de la a la z, fără diacritice. Se numeşte cuvânt un şir finit, eventual vid, de litere din alfabet. Se numeşte mască un şir de caractere din alfabet având eventual în plus caracterele ? şi * cu următoarea semnificaţie: caracterul ? înlocuieşte oricare din literele de la a la z (o singură literă) iar caracterul * înlocuieşte un cuvânt oarecare, eventual vid, format cu litere de la a la z.

Spre exemplu avem masca a?b*c. Dacă avem 3 cuvinte şi anume abbc, acbaac şi abac atunci primele 2 se potrivesc cu masca.

Cerința

Considerându-se o listă de cuvinte, să se determine:

a) Numărul de cuvinte distincte.
b) Numărul de cuvinte distincte ce se potrivesc cu o mască dată, adică se pot obţine prin înlocuirea caracterelor ? şi * din mască.

Date de intrare

Fișierul de intrare masca.in conține:

  • Pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2.
  • Pe a doua linie o mască E (şir de caractere).
  • Pe a treia linie numărul N de cuvinte.
  • Pe fiecare din următoarele N linii câte un cuvânt S (şir de caractere) cu litere din alfabet.

Date de ieșire

Fișierul de ieșire masca.out va conține:

  • Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerinţă. În acest caz, în fişierul de ieşire se va scrie un singur număr natural N1, reprezentând numărul de cuvinte distincte S din fişierul de intrare.
  • Dacă valoarea lui p este 2, se va rezolva numai punctul b) din cerinţă. În acest caz, în fişierul de ieșire se va scrie un număr natural N2, reprezentând numărul de cuvinte distincte S ce se potrivesc cu masca E.

Restricții și precizări

  • Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerinţa a doua se acordă 80 de puncte.
  • 1≤N≤1000
  • Lungimea unui cuvânt oarecare S cât şi a expresiei mască E este între 1 şi 100 de caractere.
  • În expresia mască E sunt cel mult două caractere *.

Exemplul 1

masca.in

1
a*a?b
7
ababb
aab
aabb
aab
abcaab
abcaab
ababa

masca.out

5

Explicație

Cuvintele aab si abcaab apar de cate 2 ori. Atenţie! Pentru acest test se rezolvă doar cerinţa a).

Exemplul 2

masca.in

2
a*a?b
7
ababb
aab
aabb
aab
abcaab
abcaab
ababa

masca.out

3

Explicație

Cuvintele ababb, aabb și abcaab se potrivesc cu masca. Cuvântul abcaab apare de 2 ori. Atenţie! Pentru acest test se rezolvă doar cerinţa b).

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Masca:

program sablon;
var fisier,g:text;
exp,s:string;
n,i,j,k:integer;
p:integer;
gasit:boolean;
x:array[1..1000]of string;

function f(exp,s:string):boolean;
var i:integer;ok:boolean;
begin
if exp='' then if s='' then f:=true
                       else f:=false
          else
 if (exp[1]>='a')and(exp[1]<='z') then
  if s<>'' then
   if s[1]=exp[1] then
                    begin
                    delete(exp,1,1);
                    delete(s,1,1);
                    f:=f(exp,s)
                    end
                  else {s[1]<>exp[1]} f:=false
           else {s=''} f:=false
 else
  if exp[1]='?' then
   if s<>'' then
              begin
              delete(exp,1,1);
              delete(s,1,1);
              f:=f(exp,s)
              end
            else f:=false
  else {exp[1]='*'}
   begin
   delete(exp,1,1);
   ok:=f(exp,s);
   for i:=1 to length(s) do
    begin
    delete(s,1,1);
    ok:=ok or f(exp,s);
    end;
   f:=ok;
   end;
end;

begin
assign(fisier,'masca.in');
reset(fisier);
readln(fisier,p);
readln(fisier,exp);
readln(fisier,n);
if p=2 then
begin
k:=0;
for i:=1 to n do
 begin
 readln(fisier,s);
 if f(exp,s) then
  begin
  gasit:=false;
  for j:=1 to k do
   if s=x[j] then gasit:=true;
  if not(gasit) then
   begin inc(k);
   x[k]:=s;
   end;
  end;
 end;
close(fisier);
end
else
begin
k:=0;
for i:=1 to n do
 begin
 readln(fisier,s);
  begin
  gasit:=false;
  for j:=1 to k do
   if s=x[j] then gasit:=true;
  if not(gasit) then
   begin inc(k);
   x[k]:=s;
   end;
  end;
 end;
close(fisier);
end;

{writeln(exp);
for j:=1 to k do
 writeln(x[j],' DA');

writeln('nr=',k);}

assign(g,'masca.out');
rewrite(g);
writeln(g,k);
close(g);
end.

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1493 Masca

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1493 Masca de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!