시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 37 | 19 | 16 | 59.259% |
不運なイクタ君は持っていた大事な文字列$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行に出力せよ。
abcbcdbc abc
2
$S$の3番目の文字から始まるcbc, $S$の6番目の文字から始まるdbcが条件を満たす。
aaaaaa aaaaaa
0
完全に一致する文字列は数えてはならない。
baaaaaaaa b
8