カエサルの数え上げ

2 secs 1024 MB
magurofly's icon magurofly

問題

ストーリー

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

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

例えば、 mojacoder11 つずらすと npkbdpefs になります。


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

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

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

問題文

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

文字列 SS の中に TT のシフト は何個含まれていますか?

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

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

制約

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

入力

N MSTN\ M\\ S\\ T

出力

答えを 11 行に出力せよ。

入出力例

入力例1
9 2
mojacoder
ac
出力例1
2

mojacoder には ac11 つ、 mo11 つ含まれています。 よって、 ac のシフトは合計 22 つ含まれています。

入力例2
44 2
The quick brown fox jumps over the lazy dog.
if
出力例2
3

ro11 つ、 he22 つ含まれます。

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

入力例3
26 5
ABCDEFGHIJKLMNOPQRSTUVWXYZ
ABCDE
出力例3
22

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

提出


Go (1.21)