問題
http://topcoder.bgcoder.com/print.php?id=1201
あるテキストが与えられ、そのテキストは元の回文の前半を切り出したサブ文字列である。
また、辞書に存在する文字列の集合が与えられる。
このとき、元の文字列を辞書に存在する文字列に順に分割したい。
ただし、分割の方法が複数ある場合は辞書順で最も先にくるものを返す。
解き方
回文は元の文字列の最後の文字を繰り返すものと繰り返さないものの２通りあるため、
この２通りについて分割できるか調べる。
まずは元の文字列をsetに格納してどこからどこまで分割可能か判定する。
次にｄｐを用いて、ｄｐ[n]を最後からn番目の文字まで分割可能であるかどうかを表してあげる。
dp[0]まで漸化式的に走査し、dp[0]が1であれば答えは存在するので、今度は順に判定していき文字列の分割を行う。
コード
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()
set<string> w;
class Palindromist {
public:
string solve(string text){
int n=text.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(text.substr(i,j-i))!=w.end())can[i][j]=1;
int 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]&&can[i][j])dp[i]=1;
if(!dp[0])return "";
string ret="";
int pos=0;
while(pos<n){
for(int i=pos+1;;i++){
if(can[pos][i]&&dp[i]){
ret+=' '+text.substr(pos,i-pos);
pos=i;
break;
}
}
}
return ret.substr(1);
}
string palindrome(string text, vector<string> words) {
w.clear();
FORE(i,0,words.size())w.insert(words[i]);
string text2=text;
reverse(all(text2));
string ans1=solve(text+text2);
string ans2=solve(text+text2.substr(1));
if(ans1.empty()&&ans2.empty())return "";
if(ans1.empty())return ans2;
if(ans2.empty())return ans1;
return min(ans1,ans2);
}
};
#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()
set<string> w;
class Palindromist {
public:
string solve(string text){
int n=text.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(text.substr(i,j-i))!=w.end())can[i][j]=1;
int 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]&&can[i][j])dp[i]=1;
if(!dp[0])return "";
string ret="";
int pos=0;
while(pos<n){
for(int i=pos+1;;i++){
if(can[pos][i]&&dp[i]){
ret+=' '+text.substr(pos,i-pos);
pos=i;
break;
}
}
}
return ret.substr(1);
}
string palindrome(string text, vector<string> words) {
w.clear();
FORE(i,0,words.size())w.insert(words[i]);
string text2=text;
reverse(all(text2));
string ans1=solve(text+text2);
string ans2=solve(text+text2.substr(1));
if(ans1.empty()&&ans2.empty())return "";
if(ans1.empty())return ans2;
if(ans2.empty())return ans1;
return min(ans1,ans2);
}
};