問題
http://topcoder.bgcoder.com/print.php?id=218
ある文字列を、与えられた辞書中の文字に分割したい。
ただし、分割の方法が複数ある場合は"AMBIGOUS!"、ない場合は"IMPOSSIBLE!"を返す。
解き方
与えられた文字列をi,jの位置で分割できるかの配列を作り、dpにてどこまで分割できるかを判定する。
複数あるかを判断するのでdpの値を足していくが、intの値をオーバーフローしないように注意が必要。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class MessageMess {
public: string restore(vector<string> dictionary, string message) {
set<string> w;
w.clear();
FORE(i,0,dictionary.size())w.insert(dictionary[i]);
int n=message.size();
int can[n+1][n+1];
memset(can,0,sizeof(can));
FORE(i,0,n+1)FORE(j,0,n+1)if(i<j && w.find(message.substr(i,j-i))!=w.end())can[i][j]=1;
long long dp[n+1];
memset(dp,0,sizeof(dp));
dp[n]=1;
for(int i=n-1;i>=0;i--)for(int j=i+1;j<=n;j++)if(dp[j]>0&&can[i][j])dp[i]+=dp[j];
if(dp[0]>1)return "AMBIGUOUS!";
if(dp[0]==0)return "IMPOSSIBLE!";
string ret="";
int x=0;
while(x<n){
for(int i=x+1;;i++){
if(dp[i]&&can[x][i]){
ret+=' '+message.substr(x,i-x);
x=i;
break;
}
}
}
return ret.substr(1);
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class MessageMess {
public: string restore(vector<string> dictionary, string message) {
set<string> w;
w.clear();
FORE(i,0,dictionary.size())w.insert(dictionary[i]);
int n=message.size();
int can[n+1][n+1];
memset(can,0,sizeof(can));
FORE(i,0,n+1)FORE(j,0,n+1)if(i<j && w.find(message.substr(i,j-i))!=w.end())can[i][j]=1;
long long dp[n+1];
memset(dp,0,sizeof(dp));
dp[n]=1;
for(int i=n-1;i>=0;i--)for(int j=i+1;j<=n;j++)if(dp[j]>0&&can[i][j])dp[i]+=dp[j];
if(dp[0]>1)return "AMBIGUOUS!";
if(dp[0]==0)return "IMPOSSIBLE!";
string ret="";
int x=0;
while(x<n){
for(int i=x+1;;i++){
if(dp[i]&&can[x][i]){
ret+=' '+message.substr(x,i-x);
x=i;
break;
}
}
}
return ret.substr(1);
}
};