Google Code Jam Japan 2011 本戦 C. ワイルドカード

Google Code Jam

C : ワイルドカード

  • 以下のようなDP配列 dp[i][j] を用意する
    • i : aにマッチし、最後の"*"を除くとi文字目までマッチするパターン
    • j : bにマッチし、最後の"*"を除くとj文字目までマッチするパターン
      • j = b.size()+1 のときはbにマッチしないパターンを表す
  • 初期化はaの接頭辞 + "*" のパターンで行う
    • dp[0][0] = "*"
    • if(a[0,i] = b[0,i]) dp[i][i] = a[0,i] + "*";
    • else dp[i][b.size()+1] = a[0] + "*";
  • DP表の更新は、aのi文字目からの部分文字列を使って行う
    • a[i,k] : aのi文字目からk文字目までを取り出した部分文字列
    • bのj文字目以降で、a[i,k] が出現する最左位置をpとする
    • a[i,k]が出現する場合は、
      • dp[k][p+(k-i+1)] = min(dp[k][p+(k-i+1)], dp[i][j] + a[i,k] +"*")
      • この場合は新しいパターンの最後に"*"をつけておけばbにマッチする
    • a[i,k]が出現しない場合は、a[i,k]を足すとbにマッチしないパターンになるので、
      • dp[k][b.size()+1] = min(dp[k][b.size()+1], dp[i][j] + a[i,k] + "*")
    • k == a.size()-1 の場合は、特別処理が必要
      • dp[i][j] + a[i,k] の後に"*"をつけなくても a全体 にマッチするパターンになる
      • このパターンは、a[i,k]がbの接尾辞となっていなければマッチしない
      • このとき、dp[k][b.size()+1] = min(dp[k][b.size()+1], dp[i][j] + a[i,k])
  • ちなみに、今回の文字列比較の定義では A < B なら AC < BC が成り立つ
  • ので、このような動的計画法で最短のものを求めていって良い
  • 計算量はO(n^4)だけど、ジャッジデータに対して20秒近くかかった

書いてみたコード

#include <iostream>
#include <string>

using namespace std;

string comp(string a, string b){
    if(a=="") return b;
    if(b=="") return a;
    if(a.size() != b.size())
        return a.size() < b.size() ? a : b;
    int cntA = 0, cntB = 0;
    for(int i=0;i<a.size();i++) if(a[i]=='*') cntA++;
    for(int i=0;i<b.size();i++) if(b[i]=='*') cntB++;
    if(cntA != cntB)
        return cntA < cntB ? a : b;
    return a < b ? a : b;
}

string solveLarge(string a, string b){
    int n = a.size(), m = b.size();
    string dp[52][52];

    for(int i=0;i<=n+1;i++)
        for(int j=0;j<=m+1;j++) dp[i][j] = "";
    dp[0][0] = "*";

    for(int i=0;i<n;i++){
        if(i>=m || a[i]!=b[i]){
            dp[i+1][m+1] = a.substr(0, i+1) + "*";
            break;
        } else {
            dp[i+1][i+1] = a.substr(0, i+1) + "*";
        }
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<=m+1;j++)
            dp[i+1][j] = comp(dp[i+1][j], dp[i][j]);
        for(int j=0;j<=m;j++){
            if(dp[i][j] == "") continue;
            string pat = "";
            int l = 0;
            for(int k=i;k<n;k++){
                pat += a[k];
                l++;
                int p = b.find(pat, j);
                if(p == string::npos){
                    dp[k+1][m+1] = comp(dp[k+1][m+1], dp[i][j]+pat+"*");
                    break;
                }
                else {
                    dp[k+1][p+l] = comp(dp[k+1][p+l], dp[i][j]+pat+"*");
                }
            }
            pat = a.substr(i);
            if(b.find(pat, max(j, m-(int)pat.size())) == string::npos){
                dp[n][m+1] = comp(dp[n][m+1], dp[i][j]+pat);
            }
        }
    }
    return comp(a, dp[n][m+1]);
}

int main(){
    int TEST; cin >> TEST;
    for(int test=1;test<=TEST;test++){
        string a, b; cin >> a >> b;
        printf("Case #%d: %s\n", test, solveLarge(a, b).c_str());
    }
}