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 $[|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.

Restricţii si precizări

• $1 \leq |A|, |B| \leq 1 \ 000 \ 000$;
• $1 \leq x \leq [|B|/2], |B| =$ 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.