[Usaco2007 Feb]The Cow Lexicon

Time Limit:5000MS  Memory Limit:65536K
Total Submit:8 Accepted:7
Case Time Limit:1000MS

Description

没有几个人知道,奶牛有她们自己的字典,里面的有W (1 ≤ W ≤ 600)个词,每个词的长度不超过25,且由小写字母组成.她们在交流时,由于各种原因,用词总是不那么准确.比如,贝茜听到有人对她 说"browndcodw",确切的意思是"browncow",多出了两个"d",这两个"d"大概是身边的噪音.

奶牛们发觉辨认那些奇怪的信息很费劲,所以她们就想让你帮忙辨认一条收到的消息,即一个只包含小写字母且长度为L (2 ≤ L ≤ 300)的字符串.有些时候,这个字符串里会有多余的字母,你的任务就是找出最少去掉几个字母就可以使这个字符串变成准确的"牛语"(即奶牛字典中某些词 的一个排列).

Input

第1行:两个用空格隔开的整数,W和L.
第2行:一个长度为L的字符串,表示收到的信息.
第3行至第W+2行:奶牛的字典,每行一个词.

Output

唯一一行:一个整数,表示最少去掉几个字母就可以使之变成准确的"牛语".

Sample Input

6 10
browndcodw
cow
milk
white
black
brown
farmer

Sample Output

2

Source

一般来说对付这种字符串匹配的问题都是要用Dp的。。
这道题用Dp（i,s,p）表示当前第匹配到第i个字符，最末是第s个单词的长为p的前缀。。
然后对于每个字符开个vector记录出现过的位置，同时用MaxEnd记录当时可以开新串的位置的Dp最大值（用于转移串的第一个顶点）。。注意vector要排个序以防止后效性。。
就可以了。。具体看Code吧(*^__^*) 嘻嘻。。
Code：

#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
const int inf=~0U>>2,maxw=600,maxn=300,maxl=26;
using namespace std;
string S[maxw],A;
int w,l;
int Dp[maxw][maxl]={0};
struct state
{
int s,p;
state(int _s,int _p):s(_s),p(_p){}
bool operator<(const state&o)const
{return p>o.p;}
};
vector<state> P[maxl];
int main()
{
//freopen("in","r",stdin);
cin>>w>>l;
cin>>A;
rep(i,w)
{
cin>>S[i];
rep(j,S[i].size())
{
P[S[i][j]-‘a’].pb(state(i,j));
Dp[i][j]=-inf;
}
}
rep(i,26)sort(P[i].begin(),P[i].end());
int MaxEnd=0;
rep(t,l)
{
int c=A[t]-‘a’;int nextMaxEnd=MaxEnd;
for(vector<state>::iterator i=P.begin();i!=P.end();i++)
{
if(!i->p)Dp[i->s][i->p]=MaxEnd+1;
else Dp[i->s][i->p]>?=Dp[i->s][i->p-1]+1;
if(i->p==S[i->s].size()-1)nextMaxEnd>?=Dp[i->s][i->p];
}
MaxEnd=nextMaxEnd;
}
cout<<l-MaxEnd<<endl;
}