3297: [USACO2011 Open]forgot

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 69  Solved: 51

[][][]

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”。 

给你字典，贝西记得的字母，请找到她的密码。如果有一个以上的密码是可能的，找到字典序最前的。 

Input

*第1行：两个空格分隔的整数：L和NW 

*第2行：一个字符串，长度为L：P 

*第3..N+2W行：第I+2行包含在字典中的第i个字：W_i

Output

 

*第1行：密码

Sample Input

15 6

a??l?ban???????

apple

cow

farmer

banana

bananas

pies

Sample Output

Applebananapies

HINT

 

Source

 

题解：看了半天一直还在想着怎么套AC自动机，直到看到了N<=1000这个复杂度，于是感觉暴力DP都能过啦么么哒

1 /************************************************************** 2     Problem: 3297 3     User: HansBug 4     Language: Pascal 5     Result: Accepted 6     Time:1204 ms 7     Memory:2832 kb 8 ****************************************************************/ 9  10 var11    i,j,k,l,m,n:longint;12    a,b:array[0..2000] of ansistring;13    s1:ansistring;14 function check(x:longint;s2:ansistring):boolean;15          var i:longint;16          begin17               for i:=1 to length(s2) do18                   if (s1[x+i]<>'?') and (s1[x+i]<>s2[i]) then exit(false);19               exit(true);20          end;21 begin22      readln(m,n);23      readln(s1);24      for i:=1 to n do readln(a[i]);25      for i:=1 to m do26          for j:=1 to n do27              begin28                   k:=i-length(a[j]);29                   if (k<0) or ((k<>0) and (b[k]='')) then continue;30                   if check(k,a[j]) then31                      begin32                           if (b[i]='') or (b[i]>(b[k]+a[j])) then b[i]:=b[k]+a[j];33                           k:=0;34                      end;35              end;36      writeln(b[m]);37      readln;38 end.