Multilang - Wildcards


Enunciado del problema

Alice and Bob are playing a game: Alice selects a text t and a word w, and then Bob has to say how many times w occurs in t. However, after a while, Alice realizes that this version of the game is too boring for Bob and decides to make a modification: in her new version of the game, the wildcard symbol ‘?’ can occur in w any number of times. Each occurrence of ‘?’ in w can be matched with any character in t.


In the new version of the game, for instance, if the text is t = banana and the word is w = ?a?, then w occurs twice in t: at position 0 matching ban and at position 2 matching nan. Notice that matches can overlap.


Can you write a program to help Bob solve this new game?



Entrada

The input consists of two lines. The first line contains the text t and the second line contains the word w. The text t consists of lowercase letters from the English alphabet \((1 \leq |t| \leq 10^5)\), and the word w consists of lowercase letters from the English alphabet and the wildcard character ‘?’ \((1 \leq |w| \leq 10^5)\). It is guaranteed that there will be at most k wildcard characters in w, where \(0 \leq k \leq min(|w|, \frac{10^6}{|t|})\)


Salida

Print a line with one integer denoting the number of times w appears in t if each wildcard character matches any character in t.


Ejemplos


Entrada Ejemplo 1

banana
?a?

Salida Ejemplo 1

2

Entrada Ejemplo 2

bananas
?a?

Salida Ejemplo 2

3

Entrada Ejemplo 3

abide
a??d

Salida Ejemplo 3

1

Entrada Ejemplo 4

abide
a?d

Salida Ejemplo 4

0

Entrada Ejemplo 5

abracadabra
a?a

Salida Ejemplo 5

2

Entrada Ejemplo 6

acisredis
?b

Salida Ejemplo 6

0

Entrada Ejemplo 7

acisredis
??

Salida Ejemplo 7

8

Entrada Ejemplo 8

icpc
world?finals

Salida Ejemplo 8

0

Notas

"La salida debe tener un caractér de nueva línea al final del archivo, de lo contrario puede recibir el veredicto de respuesta incorrecta.".

Wildcards

Select your language