3087 - 【入门】小黄的短信

题目描述

老黄是个喜欢小狗的同学,路上遇到任何小狗,老黄都会伸出双臂,一脸甜蜜地对小狗说:“小狗,抱抱~”。不过,大多数情况下,小狗都是不会理老黄的,这点让老黄非常郁闷。

可是,就在老黄去云南旅游的路途中,碰到了一只神奇的小狗。这只小狗特别听老黄的话,而且后来一问狗的主人,才知道,这只小狗居然叫“小黄”!这下老黄小黄都高兴坏了,感觉缘分真是件奇妙的事情!

老黄经常对着小黄说话,总共对小黄说过 M1 \le M \le 1000)句话。后来老黄从云南回来了,小黄一直思念着老黄,就给老黄发短信。小黄只会发老黄跟他讲过的话,但是由于信号不好,短信从某一个地方开始的后面一段就全部丢失了,也就是说只剩下了前面一段,这样的短信在英语中被称为某句话的前缀。现在老黄收到了 N1\le N\le 10000)条短信,老黄想知道有多少条是小黄发过来的。每句话和每条短信都不超过 60 个字符。

输入

输入文件第 1 行:包含2个用空格隔开的整数 MN

输入文件第 2 行到第 M+1 行:每行描述了一句老黄对小黄说的话。

输入文件第 M+2 行到第 M+N+1 行:每行描述了一条老黄收到的短信。

输出

输出文件仅有一行只包含一个整数,表示老黄收到的短信中,是老黄对小黄说的话的前缀的短信总数。

样例

输入

3 4
I will not buy this record, it is scratched.
My hovercraft is full of eels.
Do you want to come back to my place? Bouncy, bouncy.
I will not buy this rec
My helicopter is
Do you want to come back
I will not buy this cat.

输出

2
说明

样例解释

老黄一共对小黄说过 3 句话,分别是 I will not buy this record, it is scratched. 和 My hovercraft is full of eels. 和 Do you want to come back to my place? Bouncy, bouncy. 老黄收到了 4 条短信,分别是 I will not buy this rec 和 My helicopter is 和 Do you want to come back 和 I will not buy this cat. 其中只有 I will not buy this rec 和 Do you want to come back 这两句话是小黄发给老黄的短信,因为 I will not buy this rec 是 I will not buy this record, it is scratched. 的前缀,Do you want to come back 是 Do you want to come back to my place? Bouncy, bouncy. 的前缀,只有是老黄说的话的前缀的短信,才是小黄发给老黄的短信。

数据范围

10\% 的数据满足 M \le 5, N \le 5

40\% 的数据满足 M \le 100, N \le 10000

100\% 的数据满足 M \le 1000, N \le 10000

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 27
通过人数 8
金币数量 1 枚
统计
上一题 下一题