Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 232 B 問題 Caesar Cipher

AtCoder ABC ABC232 B問題 200 pts

問題

提出解答

問題の概要

長さが等しい英小文字の列 $S,T$ が与えられる. $S$ に対して, 以下を1回行う.

非負整数 $K$ を決める.
$S$ の各文字を $K$ 個後ろにずらす.

以上の操作で $S$ を $T$ に一致できるか? ただし, $\tt{'z'}$ 以外の英小文字の1個後ろの文字は辞書式の順番であり, $\tt{'z'}$ の1個後ろは $\tt{'a'}$ とする.

制約

$S,T$ は英小文字からなる長さが $1$ 以上 $10^5$ 以下の列
$|S|=|T|$

解法

まず, $K$ を選ぶ範囲として, $K=0,1,2, \dots, 25$ の $26$ 通りに制限してもよい. そして, $S,T$ の1文字目を見ることで, $K$ として選ぶべき整数が一意に定まる. その整数 $K'$ に対して, $S$ の全ての文字を $K'$ 個ずらして $T$ と一致するかどうかの判定をすればよい.