Aparitii2

aparitii2

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

Alis şi-a descoperit o nouă pasiune: şirurile de caractere. Fiind elevă în clasa a $12$-a ea se pregăteşte pentru examenul de bacalaureat. După ce a rezolvat câteva probleme propuse şi-a dat seama că acestea sunt prea uşoare, aşa că, s-a gândit ea singură la o problemă. Astfel, Alis are două şiruri de caractere $A$ şi $B$ formate doar din litere mici ale alfabetului englez. Pentru un oarecare $x$ dat, ea se întreabă de câte ori apare şirul $B$ ca subsecvenţă în şirul $A$, ştiind că primele $x$ respectiv ultimele $x$ caractere din $B$ rămân fixate iar celelalte pot fi înlocuite cu orice caracter.
 
h2. Cerinta
 
Se dau cele $2$ şiruri $A$ şi $B$. Se cere să se afişeze pentru fiecare $x$ de la $1$ la jumatatea lungimii şirului $B$ de câte ori apare şirul $B$ în $A$ ştiind că primele $x$ respectiv ultimele $x$ caractere din $B$ rămân fixate iar celelalte pot fi înlocuite cu orice caracter.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $aparitii2.in$ conţine pe prima linie şirul $A$ iar pe a doua linie şirul $B$.

Fişierul de intrare $aparitii2.in$ ...

h2. Date de ieşire

În fişierul de ieşire $aparitii2.out$ se vor afişa $[|B|/2]$ linii, pe fiecare linie $i$ aflându-se numărul de apariţii al şirului $B$ în şirul $A$, cu restricţiile specificate.

În fişierul de ieşire $aparitii2.out$ ...

h2. Restricţii

* $1 ≤ |A|, |B| ≤ 1 000 000$
* $1 ≤ x ≤ [|B|/2], |B| = lungimea şirului B$

* $... ≤ ... ≤ ...$

h2. Exemplu

table(example). |_. aparitii2.in |_. aparitii2.out |_. Explicatie |
| abzdeazxye
abcde
| 2
1
| Pe prima linie se află răpunsul pentru i=1, astfel, rămâne fixat primul respectiv ultimul caracter din sirul B: a***e.
Astfel, sunt două apariţii în şirul A: abzde, azxye.
Pe a doua linie se află răspunsul pentru i=2, astfel, rămân fixate primele două respectiv ultimele două caractere: ab*de.
Există o apariţie în A: abzde.
|

table(example). |_. aparitii2.in |_. aparitii2.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

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