同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

22054_单词缩写

2022-5-16 18:21| 发布者: Hocassian| 查看: 22| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-4-8950672592700-Problem List-采集的数据-后羿采集器.html

Pro.ID

22054

Title

单词缩写

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=22054

AC

Submit

Ratio

时间&空间限制

Time Limit: 1500/500 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

描述

Alice发现好多计算机中的单词都是缩写，如GDB，它是全称Gnu DeBug的缩写。但是，有时缩写对应的全称会不固定，如缩写LINUX，可理解为：

(1) LINux's UniX

(2) LINUs's miniX

(3) Linux Is Not UniX

现在Alice给出一个单词缩写，以及一个固定的全称（若干个单词组成，空格隔开）。全称中可能会有无效的单词，需要忽略掉，一个合法缩写要求每个有效单词中至少有一个字符出现在缩写中，缩写必须按顺序出现在全称中。

对于给定的缩写和一个固定的全称，问有多少种解释方法？解释方法为缩写的每个字母在全称每个有效单词中出现的位置，有一个字母位置不同，就认为是不同的解释方法。

输入

第一行输入一个N，表示有N个无效单词；

接下来N行分别描述一个由小写字母组成的无效单词；

最后是若干个询问，先给出缩写（只有大写字母），然后给出一个全称，读入以 "LAST CASE" 结束。

1 <= N <= 100，每行字符串不超过150，询问不超过20

输出

Description

Alice发现好多计算机中的单词都是缩写，如GDB，它是全称Gnu DeBug的缩写。但是，有时缩写对应的全称会不固定，如缩写LINUX，可理解为：

(1) LINux's UniX

(2) LINUs's miniX

(3) Linux Is Not UniX

Input

第一行输入一个N，表示有N个无效单词；

接下来N行分别描述一个由小写字母组成的无效单词；

最后是若干个询问，先给出缩写（只有大写字母），然后给出一个全称，读入以 "LAST CASE" 结束。

1 <= N <= 100，每行字符串不超过150，询问不超过20

Output

对于每个询问先输出缩写，如果当前缩写不合法，则输出"is not a valid abbreviation"，否则输出"can be formed in i ways" （i 表示解释方法种数）。

最后方案数不超过10⁹

Sample Input

and

ACM academy of computer makers

RADAR radio detection and ranging

LAST CASE

Sample Output

ACM can be formed in 2 ways

RADAR is not a valid abbreviation

样例输入