[USACO Feb07]奶牛词典

成绩 0 开启时间 2013年01月18日 星期五 13:15
折扣 0.8 折扣时间 2013年01月18日 星期五 13:15
允许迟交 是 关闭时间 2013年01月18日 星期五 13:15
输入文件 lexicon.in 输出文件 lexicon.out

译: zqzas


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


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


输入格式:

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

输出格式:

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

样例输入: 

6 10
browndcodw
cow
milk
white
black
brown
farmer


样例输出 

2