|
||||||||||
昵称检索Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 1538 Accepted Submission(s): 399 Problem Description 给定一个字符串 $S$,请计算从中删去一部分字符后(可以什么都不删),可以得到多少个本质不同的''昵称''。 一个字符串被认为是''昵称''当且仅当它可以被划分成前后两个部分,第一个部分是给定的 $n$ 个名字之一,第二个部分长度固定四位,表示生日。 例如第一个样例中,可以得到的''昵称''分别为:''$\texttt{kevin0724}$''、''$\texttt{kevin0729}$''、''$\texttt{kevin0924}$''、''$\texttt{kevin0929}$''。 Input 第一行包含一个正整数 $T$ ($1\leq T\leq 100$),表示测试数据的组数。 每组数据第一行包含两个正整数 $n,m$ ($1\leq n\leq 10^5$, $1\leq m\leq 10^6$),分别表示名字的数量以及字符串 $S$ 的长度。 第二行包含一个长度为 $m$ 的字符串 $S$,由数字和小写英文字母构成。 接下来 $n$ 行,每行一个长度在 $[1,20]$ 之间的仅由小写英文字母构成的字符串 $name_i$,表示一个名字。输入数据保证名字两两不同。 输入数据保证 $\sum m\leq 7\,000\,000$,且 $\sum |name|\leq 7\,000\,000$。 Output 对于每组数据输出一行一个整数,即能得到的本质不同的''昵称''数量。 Sample Input
Sample Output
Source | ||||||||||
|