SRM 497 Div2 Hard MakeSquare

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=8681&rd=14426

同じ文字列を２つ結合してできた文字列をSquareな文字列という。文字列Sから好きな文字を取り除く、変更する、挿入するという操作を行うことでSquareな文字列にするための最小の操作を求めよ。

やりかた

編集距離についての問題。全探索は調べ切れないので候補を絞りたい。
文字列Sを図のようにAとBという２つに分けた時に

調べればいい候補となるのは S -> AA か S -> BB である。
例えばabcdabcを(abcd) (abc)とわけたら、調べればいいのはabcdabcdかabcabcまでの編集距離である。
(a) (bcdabc)と分けたらaaかbcdabcbcdabcまでの編集距離である。ただしこの場合は操作最小にはならない。

こんなかんじでSの分け方を決めて、分けた２つに対し、それぞれおなじ文字列をくっつけてSquareな文字列にして編集距離をとればいい。

以下ソース。

class MakeSquare {
public:
  //編集距離
  int levenDist(string s, string t){
    int cost = 1;
    vector<vector<int> > dp(s.length() + 1, vector<int>(t.length() + 1, 0));
    for(int i = 0; i <= (int)s.length(); i++) dp[i][0] = i;
    for(int i = 0; i <= (int)t.length(); i++) dp[0][i] = i;
    for(int i = 0; i < (int)s.length(); i++)
      for(int j = 0; j < (int)t.length(); j++)
	dp[i + 1][j + 1] = min(dp[i + 1][j] + 1, 
			       min(dp[i][j + 1] + 1, 
				   dp[i][j] + ((s[i] == t[j]) ? 0 : cost)));
    return dp[s.length()][t.length()];
  }
  int minChanges(string S) {
    int result = INF;
    for(int i = 0; i <= (int)S.length(); i++){
      result = min(result, min(levenDist(S, S.substr(0, i) + S.substr(0, i)), 
			       levenDist(S, S.substr(i) + S.substr(i))));
    }
    return result;
  }
};

これはぼんやり考えていたらできた。やった。
編集距離もライブラリ化しておこう。