Se dau un text şi o mască formate din litere mici ale alfabetului englez. În plus, în mască pot apărea caracterele speciale ? şi *.
Spunem că masca se potriveşte peste o subsecvenţă din text dacă şi numai dacă înlocuind fiecare caracter ? cu exact o literă (câte o literă pentru fiecare ? din mască) şi fiecare * cu o secvenţă de litere (eventual vidă; câte una pentru fiecare * din mască) se obţine subsecvenţa .
Două potriviri peste aceeaşi subsecvenţă sunt considerate diferite dacă există cel puţin un character special care se înlocuieşte cu un caracter/secvenţă de pe alte poziţii din în cele două potriviri. De asemenea, două potriviri peste subsecvenţe diferite din text sunt considerate distincte. Două subsecvenţe sunt considerate diferite dacă se găsesc pe poziţii diferite în text, chiar dacă ele sunt egale dacă le comparăm ca string-uri.
Cerinţă
Aflaţi numărul de potriviri distincte ale măştii în text.
Date de intrare
Pe prima linie a fişierului de intrare pattern.in se găseşte un număr care reprezintă numărul de teste. Urmează câte două linii pentru fiecare test: pe prima linie textul iar pe a doua masca pentru testul respectiv.
Date de ieșire
În fişierul de ieşire pattern.out se vor găsi linii conţinând câte un singur număr egal cu numărul posibilităţilor de potrivire a măştii în text modulo pentru fiecare test.
Restricții și precizări
- Pentru din teste: şi
- Numărul caracterelor speciale din mască va fi mai mic decât .
- În mască nu vor exista două
*alăturate şi există cel puţin o literă.
Exemplu
pattern.in
3
aababba
a?b*
abbabbcbaba
?c?
aaa
a*a*
pattern.out
7
1
4
Explicație
În primul test avem următoarele potriviri: aababba, aababba, aababba, aababba, aababba, aababba, aababba.
Pentru al doilea test avem o singură potrivire: abbabbcbaba.
Pentru al treilea test avem potrivirile (caracterele subliniate sunt potrivite peste *): aaa, aaa, aa, aa