2716 - 英文写作

题目描述

A 这学期开始学习英语啦。虽然只学了少量的单词,但 Linda 老师鼓励同学们要用已经学过的单词,尽量的尝试英文写作。

在老师的鼓励下,小 A 写了自己的第一篇小短文。由于学习时间不长,小 A 写错了一些单词。奇怪的是,A 写错的每个单词,都是在正确的单词的基础上,多写了一个或多个字母。比如,小 A 可能会将 hello 错误的写成 helloa,或者将 man 错误的写成 imann,或者将 car 错误的写成 catr

A 将小短文发给 Linda 老师后,细心的 Linda 老师决定帮忙修改错误的单词。

现在,给出小 A 已经学习过的所有的单词,并给出小 A 写的这篇小短文。请编程计算出,Linda 老师至少需要删除几个字母,才能使得小 A 写的这篇小短文中,所有的单词都是正确的。

更具体的信息,请参考本题的输入、输出描述以及对于样例 1 的分析。

输入

1 行输入两个整数 NL,分别表示小 A 已经学习了 N 个单词,小 A 写的小短文长度为 L

2 行,有一个长度为 L 的仅包含英文小写字母的字符串,代表小 A 写的小短文。(假设小 A 写的短文不含空格)

接下来 N 行,每行一个仅包含英文小写字母的单词,表示小 A 学习的 N 个单词。请注意,这 N 个单词中可能存在重复的单词。

输出

输出 Linda 老师最少需要删除字母的数量。

请注意:你不用考虑 Linda 老师修改后的小短文是否有语法错误,只要保证,小短文中的每个单词在这 N 个单词中都能正确的找到。

样例

输入

6 15 
iblikedeatemeat
like
i
you
meat
eat
alike

输出

3

输入

5 18
ialikedemyoumomama
alike
liked
you
my
mom

输出

7

输入

9 31
mandoutsoutredsetedemomomomoabc
mom
momo
outs
out
man
mad
set
red
ted

输出

7
说明

样例 1 说明

A 学习了 6 个单词,小短文的长度为 15

将小短文中加粗的字母删除:iblikedeatemeat,得到:ilikeeatmeat。即:删除 3 个字母,即可得到分别包含 i like eat meat 几个正确单词的小短文。

样例 2 说明

样例 2 删除如下 7 个加粗的字母:ialikedemyoumomama

或者,删除如下 7 个加粗的字母:ialikedemyoumomama

都可以满足题意。

数据范围

对于 100\% 的数据,满足 1 \le N \le 6002 \le L \le 300,每个单词的长度均在 [1,30] 的范围内。

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 基础


上一题 下一题