解説

シーザー暗号は世界で最も知られている暗号の一つです。

シーザー暗号のうちアルファベット順で $13$ ずらすものは ROT13 と呼ばれ、広く利用されています。

---

ここでは文字の種類数を $K$ とします。

バイトをそのまま扱う場合は、 $K \le 256$ となりますが、制御文字などを除けば、 $K \le 96$ です。

全探索 $O(K (N - M) M)$ (想定 TLE 解)

$S$ のすべての位置に対して、 $T$ のすべてのシフトと比較します。

これによって正しい答えは出ますが、$O(K (N - M) M)$ 回の文字の比較が必要になるため、間に合いません。

+ 差分を取る: $O((N - M) M)$

$S, T$ を観察すると、連続する $2$ 文字間の差分が一致している場合はシフトが含まれていることが見えてきます。

よって、差分を取った文字列を $S', T'$ とし、これらに対して検索することで $O((N - M) M)$ となります。

しかし、これではまだ間に合いません。

+ 線形時間の文字列検索アルゴリズムを使う (想定解): $O(N + M)$

KMP 法 や Z-Algorithm など、線形時間で文字列を検索できるアルゴリズムを使うことで $O(N + M)$ 時間でこの問題を解くことができました。