Kazun の競プロ記録

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

AtCoder Beginner Contest 279 B問題 LOOKUP

AtCoder ABC279 ABC B問題 200 pts

問題

提出解答

問題の概要

英子文字列 $S,T$ において, $T$ は $S$ の連続部分列か?

制約

$S,T$ は $1$ 以上 $100$ 以下の英小文字列.

解法

$N:=|S|, M:=|T|$ とする. $S$ における長さ $M$ の連続部分列は $1$ 以上 $N-M+1$ 以下の整数 $L$ を用いて, $S[L:L+M-1$ ] と表せる.

よって, $L=1,2, \dots, N-M+1$ の順に $S[L:L+M-1$ ] が $T$ と一致するかどうかを判定すれば良い.