学步园

这个题的最大特点是待匹配的串中有杂音。如果把字典做成hash存储，采用枚举杂音点的方法来匹配，效率是O(L*2^L)，这是没办法接受的。这样的问题我们一般要逆着来，把字典往待匹配的字符串里面代，效率可以做到O(L*W*25)。

总之，很经典很经典。

#include "string.h"<br /> #include "math.h"<br /> #include <queue><br /> #include <algorithm><br /> #include <iostream><br /> #define _clr(a,b) memset(a,b,sizeof(a))<br /> template<class T> T _abs(T a)<br /> {if(a<0) a=-a;return a;}<br /> template<class T> void Get_Min(T& a,T b)<br /> { if(a>b) a=b;}<br /> template<class T> void Get_Max(T& a,T b)<br /> { if(a<b) a=b;}<br /> using namespace std;<br /> int W,L;<br /> char str[305];<br /> char dictionary[601][26];<br /> int DP[305];<br /> int main()<br /> {<br /> scanf("%d%d",&W,&L);<br /> scanf("%s",str);<br /> for(int i=0;i<W;i++)<br /> {<br /> scanf("%s",dictionary[i]);<br /> }<br /> for(int i=0;i<=L;i++) DP[i]=i;<br /> for(int i=1;i<=L;i++)<br /> {<br /> for(int j=0;j<W;j++)<br /> {<br /> int index1=0,index2=i-1;<br /> int cnt=0;<br /> while(dictionary[j][index1]!='/0'&&str[index2]!='/0')<br /> {<br /> if(dictionary[j][index1]==str[index2])<br /> {<br /> index1++;<br /> index2++;<br /> }<br /> else<br /> {<br /> index2++;<br /> cnt++;<br /> }<br /> }<br /> if(dictionary[j][index1]=='/0')<br /> {<br /> if(DP[index2]>DP[i-1]+cnt)<br /> {<br /> DP[index2]=DP[i-1]+cnt;<br /> for(int k=index2+1;k<=L;k++)<br /> {<br /> DP[k]=min(DP[k],DP[index2]+k-index2);<br /> }<br /> }<br /> }<br /> }<br /> }<br /> printf("%d/n",DP[L]);<br /> return 0;<br /> }<br />