ZUFEOJ
Home
ProblemSet
Source/Category
Contest
Status
Ranklist
F.A.Qs
Login
Register
7608: 昵称检索
内存限制:512 MB
时间限制:3 S
题面:传统
评测方式:文本比较
上传者:
提交:6
通过:2
提交
提交记录
统计
Web Board
题目描述
定一个字符串
S
,请计算从中删去一部分字符后(可以什么都不删),可以得到多少个本质不同的''昵称''。
一个字符串被认为是''昵称''当且仅当它可以被划分成前后两个部分,第一个部分是给定的
n
个名字之一,第二个部分长度固定四位,表示生日。
例如第一个样例中,可以得到的''昵称''分别为:''
kevin0724
''、''
kevin0729
''、''
kevin0924
''、''
kevin0929
''。
输入格式
Input
第一行包含一个正整数
T
(
1
≤
T
≤
100
),表示测试数据的组数。
每组数据第一行包含两个正整数
n
,
m
(
1
≤
n
≤
1
0
5
,
1
≤
m
≤
1
0
6
),分别表示名字的数量以及字符串
S
的长度。
第二行包含一个长度为
m
的字符串
S
,由数字和小写英文字母构成。
接下来
n
行,每行一个长度在
[
1
,
20
]
之间的仅由小写英文字母构成的字符串
nam
e
i
,表示一个名字。输入数据保证名字两两不同。
输入数据保证
∑
m
≤
7
,
000
,
000
,且
∑
∣
nam
e
∣
≤
7
,
000
,
000
。
输出格式
对于每组数据输出一行一个整数,即能得到的本质不同的''昵称''数量。
输入样例
复制
2 1 18 k9e9v9i9n909792949 kevin 2 24 alicealicebobbob02290229 alice bob
输出样例
复制
4 18
分类标签
24杭电多校第四场