potrivire

Potrivire

== include(page="template/taskheader" task_id="potrivire") ==

Pentru ca a venit vara si aveti din ce in ce mai putina pofta pentru codat, v-am pregatit o problema sadetica, la care insa nu dorim o rezolvare tocmai frusta.

Pentru ca a venit vara si aveti din ce in ce mai putina pofta de codat, v-am pregatit o problema sadetica si, mai mult decat atat, acceptam solutii $barbare$ !!!

Se dau doua siruri de caractere A si B. Vi se cere sa gasiti prima aparitie a lui B in sirul A. Atentie : sirul B poate sa contine pe langa literele mici ale alfabetului englez si caracterul "*" - Acesta se potriveste cu orice subsecventa (fie ea si vida).

Se dau doua siruri de caractere A si B. Vi se cere sa gasiti prima aparitie a lui B in sirul A. Atentie : sirul B poate sa contina pe langa literele mici ale alfabetului englez si caracterul '*'. Acesta se poate inlocui cu orice subsecventa de caractere (chiar si cu cea vida).

h2. Date de intrare

Fişierul de intrare $potrivire.in$ va contine doua numere intregi N si M, reprezentand lungimea sirului A, respectiv B. Pe urmatoarele doua linii se vor afla cele doua siruri A si B.

Fişierul de intrare $potrivire.in$ va contine doua numere intregi $N$ si $M$, reprezentand lungimea sirului $A$, respectiv $B$. Pe urmatoarele doua linii se vor afla cele doua siruri $A$ si $B$.

h2. Date de ieşire

În fişierul de ieşire $potrivire.out$ se vor alfa doua numere intregi, left si right, reprezentand pozitia de inceput si de sfarsit a subsecventei sirului A care se potriveste cu sirul B. In cazul in care exista mai multe solutii se cere afisarea celei care are left minim, iar in caz de egalitate cea cu right minim.

În fişierul de ieşire $potrivire.out$ se vor afla doua numere intregi, $left$ si $right$, reprezentand pozitia de inceput si de sfarsit a subsecventei sirului A care se potriveste cu sirul B. In cazul in care exista mai multe solutii se cere afisarea celei care are $left$ minim, iar in caz de egalitate cea cu valoare $right$ minim.

h2. Restricţii

* $ 1 ≤ N, M ≤ 100 000 $
* $ numarul de caractere "*" este mai mic sau egal cu 30 $

* $1 ≤ N, M ≤ 10 000$
* numarul de caractere "*" este mai mic sau egal cu 30
* sirurile de caractere sunt indexate incepand cu pozitia 1
* in cazul in care nu exista solutie afisati -1

h2. Exemplu
table(example). |_. potrivire.in |_. potrivire.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 8 5
zxabedgh
ab*gh
| 3 8|

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="potrivire") ==

7943