22449번 - Almost Same Substring 다국어

문제

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

文字列$T'$と文書$S$が与えられる。 $S = a_{1} a_{2} a_{3} ... a_{|S|}$の長さ$|T'|$の部分文字列$a_{k} a_{k+1} ... a_{k+|T'|-1}(1 \leq k \leq |S| - |T'| + 1)$ で$T'$と比較して1文字だけ異なるものの数を求めよ。

입력

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

• 1ドル \leq |S| \leq 300,000$

• 1ドル \leq |T'| \leq |S|$

출력

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

제한

힌트