Kazun の競プロ記録

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

AtCoder Beginner Contest 287 D問題 Match or Not

AtCoder ABC287 ABC D問題 400 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

長さが等しい $2$ つの文字列 $X,Y$ に対して, 以下を満たすとき, $X,Y$ はマッチするという.

$X,Y$ に含まれる ${\tt ?}$ を独立に英小文字に置き換えることによって, $X,Y$ を一致させることができる.

このとき, $k=0,1,2, \dots, \lvert T \rvert$ に対して, 以下の問に答えよ.

$U_k$ を $S$ の先頭 $k$ 文字と末尾 $(\lvert T \rvert-k)$ 文字をこの順に連結させた文字列とする. このとき, $U_k$ と $T$ はマッチするか?

制約

$1 \leq \lvert T \rvert \leq \lvert S \rvert \leq 3 \times 10^5$
$S,T$ は英小文字列

解法

まず, 長さが等しい $2$ つの文字列 $X,Y$ に対して, 以下は同値である.

$X,Y$ はマッチする.
全てに対して, 以下が成り立つ: の文字目はとしたとき, 以下のうちの少なくともつが成り立つ.
- $x_i={\tt ?}$
- $y_i={\tt ?}$
- $x_i=y_i$

ここで, $k=1,2, \dots, \lvert T \rvert$ に対して, $U_{k-1}$ と $U_k$ の違いは $k$ 文字目だけである. このことを利用する.

集合 $E_k$ を次のようにして定義する. ただし, $U_k, T$ の $j$ 文字目を $u_{k,j}, t_j$ と書く.

$E_k=\{j \mid 1 \leq j \leq \lvert T \rvert, u_{k,j}={\tt ?} ~\lor~ t_j={\tt ?} ~\lor~ u_{k,j}=t_j\}$

このとき, $k=1,2, \dots, \lvert T \rvert$ に対して以下が成り立つ.

$E_k=\begin{cases} U_k \cup \{k\} & (u_{k,j}={\tt ?} ~\lor~ t_j={\tt ?} ~\lor~ u_{k,j}=t_j) \\ U_{k-1} \setminus \{k\} & ({\rm otherwise}) \end{cases}$

ここで, $\# U_k=\lvert T \rvert$ ならばマッチ可能, そうでなければマッチ不可能である.

なお, $E_0, E_1, \dots, E_{\lvert T \rvert}$ を一々生成する時間はないので, $E_{k-1}$ を使いまわして $E_k$ を作ることによって, 全ての $k$ に対する判定を合計で $O(\lvert S \rvert+\lvert T \rvert)$ 時間で判定できる.