Almost Same Substring

時間制限 : 4 sec, メモリ制限 : 131072 KB

不運なイクタ君は持っていた大事な文字列Tをウィルスによって異なる文字列T'に書き換えられてしまった。そのウィルスがTの1文字を異なる文字に書き換えてしまったことがわかっている。すなわちTT'はちょうど1文字のみ異なっている。イクタ君はTを復元するために、Tが出現していると思われる文書Sを用意した。Tを復元するための下準備としてSの部分文字列でTと一致している可能性があるものの個数を調べたい。

文字列T'と文書Sが与えられる。 S = a1 a2 a3 . . . a|S|の長さ|T'|の部分文字列ak ak+1 . . . ak+|T'|−1(1 ≤ k ≤ |S| − |T'| + 1)T'と比較して1文字だけ異なるものの数を求めよ。

Input

入力は以下の形式で与えられる。

S
T'
  • 1行目でSが与えられる。
  • 2行目でT'が与えられる。
  • S, T'はそれぞれ大文字、小文字のアルファベットのみからなる。

Constraints

入力中の各変数は以下の制約を満たす。

  • 1 ≤ |S| ≤ 300,000
  • 1 ≤ |T'| ≤ |S|

Output

条件を満たす部分文字列の数を1行に出力せよ。

Sample Input 1

abcbcdbc
abc

Output for the Sample Input 1

2
  • Sの3番目の文字から始まるcbc, Sの6番目の文字から始まるdbcが条件を満たす。

Sample Input 2

aaaaaa
aaaaaa

Output for the Sample Input 2

0
  • 完全に一致する文字列は数えてはならない。

Sample Input 3

baaaaaaaa
b

Output for the Sample Input 3

8

Source: ACM-ICPC Japan Alumni Group Summer Camp 2013 , Day 3, Tokyo, Japan, 2013-09-22
http://acm-icpc.aitea.net/
http://jag2013summer-day3.contest.atcoder.jp/