Kazun の競プロ記録

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

AtCoder Beginner Contest 230 B 問題 Triple Metre

AtCoder ABC ABC230 B問題 200 pts

問題

提出解答

問題の概要

$T$ を $'{\tt oxx}'$ を $10^5$ 個結合させた文字列とする. $S$ は $T$ の連続する部分列か?

制約

$S$ は $'{\tt o}', '{\tt x}'$ からなる長さ $1$ 以上 $10$ 以下の文字列

解法

速度を気にしないのであるならば, 文字列 $X$ が文字列 $Y$ の連続する部分列であるかどうかを判定する方法はたくさんある. 例えば, Python ならば, ${\tt X~in~Y}$ で判定できる.

今回, $T$ の長さは $3 \times 10^5$ で, $S$ の長さは高々 $10$ なので, このような方法でも間に合う.