TopCoder SRM 617 Div1 Hard FarStrings

問題

長さnの文字列tが与えられる。
長さnの文字列で、tとの編集距離がちょうどiであるような文字列を
1≦i≦nなるiについて出力せよ。

制約条件

n≦25
tおよび出力する文字は英小文字からなる

方針

先頭から一文字ずつ作る。
s = abc****みたいな形になっているとき、tとのマンハッタン距離の上限は、*が何ともマッチしない文字であったとき。
距離の下限は*が何ともマッチする文字であったとき。

一文字ずつ試して、残りの部分を*で埋めたとき距離の下限と上限の間に、
目標の編集距離があればよい。

ソースコード

class FarStrings {
	public:
	
	vector <string> find(string t) {
		
		int n = t.size();
		vector<string> ans;
		
		for(int d = 1; d <= n; d++){
			
			string s(n, '*');
			
			rep(i, n){
				rep(j, 26){
					s[i] = 'a' + j;
					pi x = dist(t, s);
					
					if(x.second <= d && d <= x.first) break;
				}
			}
			ans.pb(s);
		}
		return ans;
	}
	int dp[30][30], dp2[30][30];
	pi dist(const string &a, const string &b){
		
		rep(i, 30) rep(j, 30) dp[i][j] = dp2[i][j] = inf;
		rep(i, a.size() + 1) dp[i][0] = dp[0][i] = dp2[0][i] = dp2[i][0] = i;
		
		rep(i, a.size()) rep(j, b.size()){
			
			if(a[i] == b[j]){
				dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j]);
				dp2[i + 1][j + 1] = min(dp2[i + 1][j + 1], dp2[i][j]);
			}
			if(b[j] == '*') dp2[i + 1][j + 1] = min(dp2[i + 1][j + 1], dp2[i][j]);
			
			dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j + 1] + 1);
			dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i + 1][j] + 1);
			dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + 1);
			
			dp2[i + 1][j + 1] = min(dp2[i + 1][j + 1], dp2[i][j + 1] + 1);
			dp2[i + 1][j + 1] = min(dp2[i + 1][j + 1], dp2[i + 1][j] + 1);
			dp2[i + 1][j + 1] = min(dp2[i + 1][j + 1], dp2[i][j] + 1);
		}
		return mp(dp[a.size()][b.size()], dp2[a.size()][b.size()]);
	}
};