H - Almost Same Substring
Editorial
/
Time Limit: 4 sec / Memory Limit: 128 MB
不運なイクタ君は持っていた大事な文字列Tをウィルスによって異なる文字列T'に書き換えられてしまった。そのウィルスがTの1文字を異なる文字に書き換えてしまったことがわかっている。すなわちTとT'はちょうど1文字のみ異なっている。イクタ君はTを復元するために、Tが出現していると思われる文書Sを用意した。Tを復元するための下準備としてSの部分文字列でTと一致している可能性があるものの個数を調べたい。
文字列T'と文書Sが与えられる。 S = a1 a2 a3 ... a|S|の長さ|T'|の部分文字列ak ak+1 ... ak+|T'|-1(1 \leq k \leq |S| - |T'| + 1) でT'と比較して1文字だけ異なるものの数を求めよ。
Input
入力は以下の形式で与えられる。
S
T'
1行目でSが与えられる。
2行目でT'が与えられる。
S, T'はそれぞれ大文字、小文字のアルファベットのみからなる。
Constraints
入力中の各変数は以下の制約を満たす。
1 \leq |S| \leq 300,000
1 \leq |T'| \leq |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