Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | potrivire.in, potrivire.out | Sursă | FMI No Stress 2012 |
Autor | Alexandru Cazacu | Adăugată de | |
Timp execuţie pe test | 0.05 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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.
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 potriveste cu orice subsecventa de caractere (chiar si cu cea vida).
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.
Date de ieşire
Î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.
Restricţii
- 1 ≤ N, M ≤ 100 000
- numarul de caractere "*" este mai mic sau egal cu 30
- sirurile de caractere sunt indexate incepand cu pozita 1
Exemplu
potrivire.in | potrivire.out |
---|---|
7 5 zxabegh ab*gh | 3 7 |