7608: 昵称检索

内存限制:512 MB 时间限制:3 S
题面:传统 评测方式:文本比较 上传者:
提交:6 通过:2

题目描述

定一个字符串 S,请计算从中删去一部分字符后(可以什么都不删),可以得到多少个本质不同的''昵称''。
一个字符串被认为是''昵称''当且仅当它可以被划分成前后两个部分,第一个部分是给定的 n 个名字之一,第二个部分长度固定四位,表示生日。
例如第一个样例中,可以得到的''昵称''分别为:''kevin0724''、''kevin0729''、''kevin0924''、''kevin0929''。


输入格式

Input
第一行包含一个正整数 T (1T100),表示测试数据的组数。
每组数据第一行包含两个正整数 n,m (1n1051m106),分别表示名字的数量以及字符串S 的长度。
第二行包含一个长度为m 的字符串S,由数字和小写英文字母构成。
接下来n 行,每行一个长度在[1,20] 之间的仅由小写英文字母构成的字符串namei,表示一个名字。输入数据保证名字两两不同。
输入数据保证 m7,000,000,且 name7,000,000

输出格式

对于每组数据输出一行一个整数,即能得到的本质不同的''昵称''数量。


输入样例 复制

2
1 18
k9e9v9i9n909792949
kevin
2 24
alicealicebobbob02290229
alice
bob

输出样例 复制

4
18