問題

ストーリー

シーザー暗号を知っていますか？

シーザー暗号とは、文字列の各文字を、辞書順で同じだけずらしたものです。

例えば、 mojacoder を $1$ つずらすと npkbdpefs になります。

高橋君は暗号化されたメッセージを青木君から受け取りました。

二人の間では秘密の文字列が共有されていて、青木君はメッセージに含まれる秘密の文字列の個数によって秘密の内容を表現します。

ただし、秘密の文字列はずらされている可能性があります。

問題文

長さが $N, M$ である文字列 $S, T$ が与えられます。

文字列 $S$ の中に $T$ のシフト は何個含まれていますか？

ここで、ある文字列 $X'$ が文字列 $X$ のシフト であるとは、 $|X| = |X'|$ かつ、ある $0 \le d \lt 256$ が存在し、 すべての $1 \le i \le |X|$ に対して、文字コードが $X_i + d \equiv X'_i \mod 256$ であると定義します。

例えば MojaCoder のシフトは MojaCoder, NpkbDpefs, ... です。

制約

• $1 \le M \le N \le 3\times10^5$
• $S, T$ はどちらも $1$ バイト文字からなり、改行などの制御文字や文字コードが $128$ 以上の文字は含まない

入力

出力

答えを $1$ 行に出力せよ。

入出力例

9 2
mojacoder
ac

2

mojacoder には ac が $1$ つ、 mo が $1$ つ含まれています。 よって、 ac のシフトは合計 $2$ つ含まれています。

44 2
The quick brown fox jumps over the lazy dog.
if

3

ro が $1$ つ、 he が $2$ つ含まれます。

C++er 向けの情報: cin >> S では The までしか入力されないので、 std::getline(cin, S) を使いましょう。

26 5
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ABCDE

22

$S$ に含まれる $T$ のシフトは互いに重なっている場合もあります。