問題文

文字列 \(S, T, U\) が与えられます。

あなたは文字列 \(S\) の部分文字列で長さが \(T\) と同じであるものを1つ選び、 \(T\) に置き換える操作をちょうど1回行います。

置き換えた後の文字列を \(S'\) としたとき、 \(S'\) の部分文字列のうち \(U\) に一致するものの個数の最大値を求めなさい。

Note. ある文字列から連続する部分列を取った時、その文字列を元の文字列の部分文字列といいます。

入力

3行与えられ、1, 2, 3行目にはそれぞれ \(S, T, U\) が与えられる。

出力

答えを1行に出力しなさい。

制約

• \(1≦|U|≦|T|≦|S|≦10^5\)


• \(S, T, U\) は英小文字からなる文字列

小課題

小課題 Small

• \(1≦|S|≦300\)

小課題 Large

• \(1≦|S|≦3000\)

小課題 Easy Searching

• \(1≦|U|≦100\)

小課題 Euglena

• 追加の制約はない。