AOJ2090 Repeated Subsequences

問題
Repeated Subsequences | Aizu Online Judge

文字列が与えられる。適当な位置で分割したとき、最長共通部分列をとる。
最適な位置で分割したときの最長共通部分列となる文字列を出力せよ。

解法
分割して、最長共通部分列を求めればよい。よって、文字列の復元をするだけの問題。

最長共通部分列は、不一致で だけ変えずにをすすめる、一致で と の両方をすすめる、として以下のDPで書ける。

文字列の復元をする。つまり、DPの更新時にどの遷移を使ったか（最適値の更新に直接影響した元の遷移は何であるか）がわかれば良い。

:= 使用した遷移の番号(0, 1, 2)

これを利用して文字列を復元する。
文字列の復元は、初期状態, として、i, j の位置をずらせば良い。たとえば、 であれば、j だけ位置を戻す必要があるので、j-- すればよい。 であれば、i--, j-- として、同時に res += s[i]; として復元すれば良い。

const int Max = 303;

int main() {

  for(string s_; cin >> s_ && s_ != "#END";) {
    const int N = s_.size();

    string max_string;
    int max_length = 0;

    REP(k, 1, N) {
      const int sn = k;
      const int tn = N - k;
      string s = string(s_.begin(), s_.begin() + sn);
      string t = string(s_.begin() + sn, s_.end());
      int dp[Max][Max];
      int trans[Max][Max];

      zero(dp);
      minus(trans);

      rep(i, sn) {
        rep(j, tn) {
          if(s[i] == t[j]) {
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1);
            trans[i + 1][j + 1] = 0;
          }
          else if(dp[i + 1][j] > dp[i][j + 1]) {
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j]);
            trans[i + 1][j + 1] = 1;
          }
          else {
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1]);
            trans[i + 1][j + 1] = 2;
          }
        }
      }

      if(dp[sn][tn] > 0) {
        int i = sn, j = tn;
        string res;
        while(trans[i][j] >= 0) {
          if(trans[i][j] == 2) i--;
          else if(trans[i][j] == 1) j--;
          else {
            i--, j--;
            res.push_back(s[i]);
          }
        }

        if(max_length < res.size()) {
          reverse(res.begin(), res.end());
          max_length = res.size();
          max_string = res;
        }
      }
    }

    cout << max_string << endl;
  }
  
  return 0;
}