== include(page="template/taskheader" task_id="pattern") ==
Poveste şi cerinţă...
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ţă $S$ 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 $S$.
Două potriviri peste aceeaşi subsecvenţă $S$ 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 $S$ î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.
h2. Cerinţă
Aflaţi numărul de potriviri distincte ale măştii în text.
h2. Date de intrare
Fişierul de intrare $pattern.in$ ...
Pe prima linie a fişierului de intrare $pattern.in$ se găseşte un număr $T$ 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.
h2. Date de ieşire
În fişierul de ieşire $pattern.out$ ...
În fişierul de ieşire $pattern.out$ se vor găsi $T$ linii conţinând câte un singur număr egal cu numărul posibilităţilor de potrivire a măştii în text modulo $1 000 000 007$ pentru fiecare test.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 3$
* $1 ≤ lungime(text) ≤ 100 000$
* $1 ≤ lungime(mască) ≤ 50 000$
* Pentru $40%$ din teste: $lungime(text) ≤ 3 000$ şi $lungime(mască) ≤ 1 000$.
* Numărul caracterelor speciale din mască va fi mai mic decât $101$.
* În mască nu vor exista două $*$ alăturate şi există cel puţin o literă.
h2. Exemplu
table(example). |_. pattern.in |_. pattern.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3
aababba
a?b*
abbabbcbaba
?c?
aaa
a*a*
| 7
1
4
|
h3. 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 îngroşate sunt potrivite peste $*$): $aaa,aaa, a${*a*}$a, aa${*a*}
== include(page="template/taskfooter" task_id="pattern") ==
