Almost Same Substring

Time limit4sMemory limit512 MB

Summary

Count the length-|T'| substrings of S that differ from T' in exactly one character.

Level: Medium6 of 10
Topics: String, String matching, Hash map, Binary search
Solved: No attempts yet

Problem

The unlucky Ikuta had his precious string $T$ overwritten by a virus into a different string $T'$ . He knows the virus changed exactly one character of $T$ into a different character. That is, $T$ and $T'$ differ in exactly one character. To recover $T$ , Ikuta prepared a document $S$ in which he believes $T$ appears. As a step toward recovering $T$ , he wants to count the substrings of $S$ that could possibly match $T$ .

Given the string $T'$ and the document $S$ , find the number of substrings $a\_{k} a\_{k+1} ... a\_{k+|T'|-1}$ of $S = a\_{1} a\_{2} a\_{3} ... a\_{|S|}$ of length $|T'|$ ( $1 \leq k \leq |S| - |T'| + 1$ ) that differ from $T'$ in exactly one character.

Input

Each variable in the input satisfies the following constraints.

$1 \leq |S| \leq 300,000$
$1 \leq |T'| \leq |S|$

Output

Print the number of substrings satisfying the condition on one line.

Examples3

Example 1
Input
```
abcbcdbc
abc
```
Expected output
```
2
```
Example 2
Input
```
aaaaaa
aaaaaa
```
Expected output
```
0
```
Example 3
Input
```
baaaaaaaa
b
```
Expected output
```
8
```