405430: GYM101962 B Color Changing Sofa

Piva has recently bought a wonderful beach house at Praia do Forte.

After deciding that his house would be as colorful as a rainbow, Piva painted his living room in tiles of different colors. More specifically, Piva's living room can be seen as a row of $$$n$$$ tiles such that the $$$i$$$-th of them has color $$$s_i$$$, where $$$s$$$ is a string composed of lowercase English characters.

Piva now wants to put his brand-new color changing sofa in his room. The sofa is $$$m$$$ ($$$m \leq n$$$) tiles long and should be put in the room in a way that it fits entirely on $$$m$$$ consecutive tiles. Moreover, Piva wants the colors of the sofa and of the floor to match. We say that their colors match if the color of a sofa tile matches with the color of the floor tile right below it. To accomplish that, Piva may change the colors of the sofa according to its specification.

The sofa can be described by a string $$$t$$$ of zeroes and ones of length $$$m$$$, where each character in the string represents a tile of the sofa. Piva can pick the zero-tiles and change them all to the same color. The same can be done for one-tiles. Therefore, notice that it is impossible for two zero-tiles (same for one-tiles) to have different colors. Also, that means that the tiles of the sofa will have at most two different colors. For instance, suppose the string is 101. That means we can color the sofa aba or aaa, but not abc.

Given the descriptions of Piva's living room and of his sofa, determine on how many positions his sofa can be placed. Notice that for each possible placement, the sofa colors can be chosen independently. Also, notice that the sofa can be put in any direction (left to right or right to left), but a position where it can be put in both directions should be counted only once.

The first line contains the string $$$s$$$ ($$$|s| = n \leq 2000$$$) – the living room description.

The second line contains the string of zeroes and ones $$$t$$$ ($$$|t| = m \leq n$$$) – the sofa description.

Print a single integer – the number of positions the sofa can be placed.

aba
10

2

aba
111

0

aaa
101

1

abada
101

2

aab
100

1

In the first example, we can put the sofa in two positions.

1. Position $$$[1, 2]$$$, color mapping $$$(0 \rightarrow a, 1 \rightarrow b)$$$, left to right.
2. Position $$$[2, 3]$$$, color mapping $$$(0 \rightarrow b, 1 \rightarrow a)$$$, left to right.

Notice there are other correct direction and color mapping configurations for each of these positions. The ones shown above are just examples.

In the second example, there is no way to place the sofa and to choose its colors such that there is a color match.

In the third example, we can put the sofa in $$$[1, 3]$$$, color mapping $$$(0 \rightarrow a, 1 \rightarrow a)$$$, left to right.

In the fourth example, we can put the sofa in two positions:

1. Position $$$[1, 3]$$$, color mapping $$$(0 \rightarrow a, 1 \rightarrow b)$$$, left to right.
2. Position $$$[3, 5]$$$, color mapping $$$(0 \rightarrow a, 1 \rightarrow d)$$$, left to right.

In the fifth example, we can put the sofa in $$$[1, 3]$$$, color mapping $$$(0 \rightarrow a, 1 \rightarrow b)$$$, right to left.