2137: 宝典2第十一章基因序列

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

【题目描述】基因序列(GEN.cpp/c/pas)

在将要到来的星际战争中,基因武器的杀伤威力极其巨大,因此研究天顶星人的基因十分必要。魔法学院发现天顶星人的基因是一个有限的基因序列,它是由大写的英文字母A~Z组成,不同的字母表示不同种类的基因。一个基因可以分化成为一对新的基因。这种分化被一个定义的规则集合所控制。每个分化的规则可以用三个大写字母A1A2A3表示,含义为基因A1可以分化成A2A3。我们用S代表特种基因,繁殖天顶星人是从特种基因序列开始。根据给定的规则,它由被选择控制规则对基因不断进行繁殖而成。

你需要从文本文件GEN.IN 读入一个定义的规则集和一个想生成的天顶星人单词序列。对每一个给定的基因,根据给定的分化规则,检查是否它能从某一个确定特种基因序列生成,如果能,找到最小的序列长度,将结果写入文本文件GEN.OUT。

【输入格式】

在文件GEN.IN 的第一行有一个整数n,1 ≤ n ≤10000,下面n 每一行为一个分化规则。这些规则都由包含A~ Z的三个大写字母组成。

接下来有一个整数k,1≤k ≤10000,接下来的k 行有一个基因序列,基因序列由没有空格的单词组成,最多100 个英文大写字母。

【输出格式】

在文件GEN.OUT中有k行,在第I行应写入:一个正整数──需要生成第I个基因的最小长度;或者单词 NIE,如果不能生成对应的基因。

【输入样例】

6

SAB

SBC

SAA

ACA

BCC

CBC

3

ABBCAAABCA

CCC

BA

【输出样例】

3

1

NIE

加入题单

上一题 下一题 算法标签: