New Year Contest 2015 C - 文字列の書き換え
文字列が2個与えられる。任意の場所に直前の文字と違う任意の文字を挿入という操作を繰り返すとき、与えられた最初の文字列を2番めの文字列に変換できるか？
文字を追加していくと考えると、最後の文字にだけ依存する条件なのでそういったdpを構成する。
dp[i][j] をsのi文字目までのprefixからtのj文字目までのprefixが生成できるかをbooleanで持つdpテーブルとする。例えばsnukeのprefixであるsnuからsnuuが生成できるか？など。
もちろんi>jの場合は常にfalseである。dpの更新は次の2通り
- dp[i][j]がtrue、かつsのi+1文字目とtのj+1文字目が同じであればdp[i + 1][j + 1]もtrue
- 上記の条件かつtのi+1文字目がtのi + 2文字目と違うのであればdp[i][k] (k >=j) はすべてtrue
1番目は単に文字が一致してた時の話。2番目が少しわかりにくいが結局同じ文字が2個最後に並んでいるような状況でなければ任意の文字列が構成できるという話。(実験すればすぐわかる)
逆にこれ以外はfalseのまま。O(N^2)
