Aparitii

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.

Cerinţă

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.

Date de intrare

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

Date de ieşire

În fişierul de ieşire aparitii.out se vor afișa $\lfloor \frac{\lvert B \rvert}{2} \rfloor$ linii, pe fiecare linie $i$ aflându-se numărul de apariţii al șirului $B$ în şirul $A$, cu restricţiile specificate.

Restricţii si precizări

• $1 \leq \lvert A \rvert, \lvert B \rvert \leq 1 000 000$

• $ 1 \leq x \leq \lfloor \frac{\lvert B \rvert}{2} \rfloor $, $\lvert B \rvert$ = lungimea șirului $B$

Exemplu

aparitii.in

abzdeazxye
abcde

aparitii.out

2
1

Explicaţie

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.