SRM410 Div2 Hard

1000

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;
  }
};