memo [ テキストの i 文字目まで作った ][ 正規表現の j 文字目まで使った ] = pair( cost, string )
文字列の辞書順最小パスな問題は逆からやるのが吉だった気がする。
const int inf = 1 << 28; const int N = 50 + 1; pair<int, string> memo[N][N]; bool ast[N]; pair<int, string> rec(int i, int j, const string &T, const string &R) { pair<int, string> &ret = memo[i][j]; if (ret.first != -1) return ret; if (i == T.size() && j == R.size()) return ret = make_pair(0, ""); pair<int, string> mn = make_pair(inf, ""); // no more if (ast[j] && j < R.size()) { pair<int, string> tmp = rec(i, j + 1, T, R); mn = min(mn, tmp); } // one more if (ast[j] && i < T.size()) { pair<int, string> tmp = rec(i + 1, j, T, R); tmp.first += (T[i] != R[j]); tmp.second = R[j] + tmp.second; mn = min(mn, tmp); } // if (i < T.size() && j < R.size()) { pair<int, string> tmp = rec(i + 1, j + 1, T, R); tmp.first += (T[i] != R[j]); tmp.second = R[j] + tmp.second; mn = min(mn, tmp); } return ret = mn; } class ClosestRegex { public: string closestString(string T, string R) { fill(&memo[0][0], &memo[N - 1][N], make_pair(-1, "")); fill(ast, ast + N, false); for (int i = 0; i < (int)R.size(); ++i) { if (R[i] == '*') { R.erase(R.begin() + i); --i; ast[i] = true; } } pair<int, string> ret = rec(0, 0, T, R); return ret.first == inf ? "" : ret.second; } };