このセット随一の普通の問題です。
少し言い換えると、Sから'A'をいくつか削除し、Tから'B'をいくつか削除することによってSもTもUにすることができるような文字列Uが存在するかを判定すれば良いです。
「dp[i][j] = S[0]~S[i]とT[0]~T[i]を同じ文字列にできるか」というDPをします。
遷移は
- if (S[i] == 'A') dp[i+1][j] |= dp[i][j]
- if (T[j] == 'B') dp[i][j+1] |= dp[i][j]
- if (S[i] == T[j]) dp[i+1][j+1] |= dp[i][j]
の３つです。
さて、この問題を出した動機ですが、AKIBAを正規表現で解くと楽だとちょっと前に気づき、さらにそれが書かれたのブログがAdvent Calendarに投稿され、これをもう少し応用できないかと考えた結果こんな問題になりました。
正規表現解はこんな感じ(python)です。
やってることとしては、Sの先頭/各文字の間/末尾に"B*"を挿入し、"A"を"A?"に置換しています。
で、これがTにマッチすればYESです。
ただし、これでは部分点しか得られません。pythonの正規表現アルゴリズムでは*とかのマッチングを愚直なバックトラックでやっていて*の個数が増えると指数的に計算量が爆発してしまうためです。
これはなんとC++でも同様です。
ここで、Go言語やD言語やgrepなどを持ち出すと計算量がちゃんと入力長に対する線形時間であることが保証されているっぽいので間に合います。
※「入力長に対する線形時間」と言ってもO(|S|)ではなく、O(正規表現とかでかかる計算量*|S|)ということぽいので注意
あと、この正規表現にマッチするかを自力で判定しようと思ったら、dp[i][j] = Sのi文字目までが正規表現のj文字目までにマッチするかどうか、みたいなDPをやればO(正規表現の長さ*|S|)になりますね。
より良い方法として、NFAを作るというのがあります。（定数倍がよさそう）
