/ Vijos / 题库 /

遥控车

遥控车

描述

平平带着韵韵来到了游乐园,看到了n辆漂亮的遥控车,每辆车上都有一个唯一的名字name[i]。韵韵早就迫不及待地想玩名字是s的遥控车。可是韵韵毕竟还小,她想象的名字可能是一辆车名字的前缀(也就是说能确定一个i,使s是name[i]的前缀),这时她就能玩第i辆车;或者是一个无中生有的名字,即s不是任何一辆车名字的前缀,这时候她什么也不能玩。

你需要完成下面的任务:
1.韵韵想了m个她想要的名字,请告诉她能玩多少次。

2.由于管理员粗心的操作,导致每辆车的摆放位置都可能出现微小的差错,原来第i辆车现在的位置可能是i-1、i、i+1中的任意一个(第1辆车的位置不可能是0,第n辆车的位置不可能是n+1)。请你计算出共有多少种可能的排列。

注:数据保证当s是name[i]的前缀时,i是唯一确定的。一辆车可以玩多次。

格式

输入格式

第一行是2个正整数n、m。

接下来n行,每行1个字符串name[i],表示第i辆车的名字。

接下来m行,每行1个字符串s,表示韵韵想要的名字。

输出格式

第一行输出韵韵能玩的次数。

第二行输出共有多少种可能的排列。

样例1

样例输入1

4 4
Abcd
DeF
AAa
aBccc
Ab
AA
AbC
aBcc

样例输出1

3
5

限制

各个测试点1s

提示

对于题目涉及到的字符串严格区分大小写,且长度小于255。

对于20%的数据 n≤10,m≤10;
对于40%的数据 n≤1000,m≤1000;
对于100%的数据 n≤10000,m≤10000。

来源

f1zsy lizc

信息

ID
1458
难度
6
分类
字符串 | 线性代数 | 矩阵乘法高精度 点击显示
标签
递交数
522
已通过
127
通过率
24%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

重游SC theme Park NOIp2008提高组模拟赛