描述 Description
发生了这么多，贝茜已经忘记了她 cowtube 密码。然而，她记得一些有用的信息。
首先，她记得她的密码（记为变量 P）长度为 L（1 <= L<=1,000）字符串，并可以被分成一个或多个词（不一定是唯一的），词来自于字典中 NW（1<=NW<=1,000）个独特的词。一个词 W_i，被定义为一个长度 1..20 的小写字母序列(‘a’..‘z’)。她还记得她密码中某些字母的位置。
请看下面的例子。贝西知道她的密码看起来像 “a??l?ban???????”（’?’代表一个字母，她不记得），她的字典里有下面的词：
apple
cow
farmer
banana
bananas
pies
贝西有两个可能的密码是的 “applebananapies” 和“applebananascow”。
给你字典，贝西记得的字母，请找到她的密码。如果有一个以上的密码是可能的，找到字典序最前的。
输入格式 InputFormat
第 1 行：两个空格分隔的整数：L 和 NW
第 2 行：一个字符串，长度为 L：P
第 3..N+2W 行：第 I+2 行包含在字典中的第 i 个字：W_i
输出格式 OutputFormat
第 1 行：密码
样例输入 SampleInput
30 11
??r?c??b??????wucowcowf?r?n???
neal
cow
b
bb
bbb
wu
usaco
moo
moooooooo
wuuuuuuuu
farm
样例输出 SampleOutput
farmcowbbbbbbbwucowcowfarmneal
来源 Source
Silver
代码 Code
用 string 保存单词可以方便的比较字典序，接下来 DP 就好了。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
string f[1005],p,w[1005];
char ch;
inline void read(string &x)
{
x.clear();;char ch=getchar();
while ((ch<'a' || ch>'z') && ch!='?') ch=getchar();
while ((ch>='a' && ch<='z') || ch=='?') x+=ch,ch=getchar();
}
inline bool can(int a,int b)
{
int i,j,t;
t=a-w[b].length()+1;
if (t<0) return false;
for (i=t;i<=a;i++) if (p[i]!='?' && p[i]!=w[b][i-t]) return false;
return true;
}
int main()
{
scanf("%d%d",&l,&n);
read(p);
for (i=1;i<=n;i++) read(w[i]);
for (i=0;i<l;i++)
{
f[i].clear();
for (j=1;j<=n;j++) if (can(i,j))
{
t=i-w[j].length();
if (t<0) f[i]=(f[i].empty())?(w[j]):(min(f[i],w[j]));
else if ((t==0 || !f[t].empty()) && (f[i].empty() || f[i]>f[t]+w[j])) f[i]=f[t]+w[j];
}
}
cout<<f[l-1]<<endl;
return 0;
}