题意：已知原串（长度为1~1000），它由多个单词组成，每个单词除了首尾字母，其余字母为乱序，且句子中无空格。给定n个互不相同的单词（1 <= n <= 10000），问是否能用这n个单词还原出这个句子。
eg：
3
tihssnetnceemkaesprfecetsesne
5
makes
perfect
sense
sentence
this
hitehre
应输出唯一解：this sentence makes perfect sense
分析：
1、将原串从头到尾遍历，分别以原串中的每个字母为基础，查找是否有以该字母为尾字母的单词，并判断该单词是否可以在原串的这个位置形成一种构造方法，dp[i]表示从开始到第 i 位有几种构成方法，因此，状态转移方程为dp[j] += dp[i - 1]（若 i ~ j 位可以构成一个单词）
2、为了减小枚举量，通过num[]记录每个单词的字母个数,并用cnt[][]统计了元传中截止到每一位时各个字母的个数；
3、边dp边记录pre[i],以便最终输出符合要求的句子。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
typedef long long ll;
typedef unsigned long long llu;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {, , -, };
const int dc[] = {-, , , };
const double pi = acos(-1.0);
const double eps = 1e-;
const int MAXN = + ;
const int MAXT = + ;
using namespace std;
char s[MAXN];
char x[MAXT][];
int cnt[MAXN][];
int dp[MAXN];
int pre[MAXN];
int markx[MAXN];
int marky[MAXN];
struct P{
int len, id;
char st;
char num[];
P(int l, int e, char h):len(l), id(e), st(h){
memset(num, , sizeof num);
for(int i = ; i < len; ++i){
++num[x[id][i] - 'a'];
}
}
};
vector<P> v[];
bool judge(int a, int b, P &x){
if(a == ){
for(int i = ; i < ; ++i){
if(x.num[i] != cnt[b][i]) return false;
}
return true;
}
else{
for(int i = ; i < ; ++i){
if(x.num[i] != cnt[b][i] - cnt[a - ][i]) return false;
}
return true;
}
}
int main(){
int T;
scanf("%d", &T);
while(T--){
for(int i = ; i < ; ++i){
v[i].clear();
}
memset(s, , sizeof s);
memset(x, , sizeof x);
memset(cnt, , sizeof cnt);
memset(dp, , sizeof dp);
memset(pre, -, sizeof pre);//不能初始化为0，这样会漏掉第一个字母是第一个单词这种情况
memset(markx, , sizeof markx);
memset(marky, , sizeof marky);
scanf("%s", s);//原串
int l = strlen(s);
++cnt[][s[] - 'a'];
for(int i = ; i < l; ++i){//记录截止到原串中第i个字母时26个字母每个字母的个数
for(int j = ; j < ; ++j){
cnt[i][j] = cnt[i - ][j];
}
++cnt[i][s[i] - 'a'];
}
int n;
scanf("%d", &n);
for(int i = ; i < n; ++i){
scanf("%s", x[i]);
int len = strlen(x[i]);
char tmp = x[i][];
v[x[i][len - ] - 'a'].push_back(P(len, i, tmp));//以单词的尾字母为下标,每个单词初始化长度，标号和首字母三个属性
}
for(int i = ; i < l; ++i){//分别以原串中的每个字母为基础，在vector中查找以该字母为尾字母的单词，并且该单词的首字母在原串中该字母的位置之前出现
int t = v[s[i] - 'a'].size();
for(int j = ; j < t; ++j){
P& w = v[s[i] - 'a'][j];
int tmp = i - w.len + ;//该字母的首字母在原串中所对应的下标
if(tmp == && w.st == s[tmp] && judge(tmp, i, w)){//若查找到的这个单词是原串中的第一个单词且匹配
++dp[i];
markx[i] = s[i] - 'a';
marky[i] = j;
}
else if(tmp > && w.st == s[tmp] && judge(tmp, i, w) && dp[tmp - ]){//tmp>0,不是tmp!=0
dp[i] += dp[tmp - ];
pre[i] = tmp - ;
markx[i] = s[i] - 'a';
marky[i] = j;
}
}
}
if(!dp[l - ]){
printf("impossible\n");
}
else if(dp[l - ] > ){
printf("ambiguous\n");
}
else{
stack <pair<int, int> > ss;
while(!ss.empty()) ss.pop();
for(int i = l - ; i != -; i = pre[i]){//##########
ss.push(pair<int, int>(markx[i], marky[i]));
}
bool flag = true;
while(!ss.empty()){
pair<int, int> w = ss.top();
ss.pop();
if(flag) flag = false;
else printf(" ");
printf("%s", x[v[w.first][w.second].id]);
}
printf("\n");
}
}
return ;
}