Count Similar Substrings (Microsoft India)

Two strings are similar if they are equal, or if they become equal after swapping one pair of adjacent characters in one of them. Count the contiguous substrings of text that are similar to key. Overlaps are allowed, and each starting position is counted once.

输入格式

The first line contains key and the second line contains text, both consisting of lowercase English letters, with 1≤|key|≤|text|≤50.

输出格式

Output a single integer, the answer.

样例 1

输入：

moon
monomon

输出：

2

样例 2

输入：

aaa
aaaa

输出：

2

样例 3

输入：

xxy
zxxyxyx

输出：

3

样例说明

Example 1: mono (swap its last two letters) and omon (swap its first two letters) both become moon, giving 2 starting positions.

Example 2: both windows of length 3 equal aaa and need no swap; each is counted once, so the answer is 2.

Example 3: xxy at start 1 and xyx at starts 2 and 4 are all similar, for a total of 3.