Skip to content

14285: 【原4285】乔鲁诺乔巴拿的梦想

题目

题目描述

author: dhc 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4285

问题描述

乔鲁诺·乔巴拿曾经有很多梦想, 但最近他有些遗忘了.

他只记得自己的梦想都是小写字符串, 以及他最初拥有一个大写字母和$n$个替换规则. 规则分为两类, 一类是将某个大写字母替换为一个小写字母, 另一类是将某个大写字母替换为至少两个(大写小写任意的)字母.

一个小写字符串是可被生成的, 当且仅当它可以从最初的大写字母通过一些替换得到.

一个小写字符串是无歧义的, 当且仅当只能通过一系列唯一的替换得到.

例如, 如果乔鲁诺最初拥有A和规则:

A -> BC
B -> bD
C -> Dc
A -> a
A -> a
B -> b
B -> d
C -> c
D -> d

那么bdc是有歧义的:

A -> BC -> bDC -> bdC -> bdc
A -> BC -> BDc -> bDc -> bdc

ddc是没有歧义的:

A -> BC -> BDc -> dDc -> ddc

bbb是不可被生成的.

需要注意的是: 重复的规则视为不同的规则. 例如, 在以上规则中, a歧义的.

乔鲁诺知道, 自己的愿望都是在这一套规则下可被生成的, 并且一个好的愿望是无歧义的.

现在他有$m$个小写字符串, 乔鲁诺想要知道它们是否可能是自己的愿望(即, 是否可以被生成); 如果可能是的话, 它们是否是好的愿望(即, 是否有歧义).

输入格式

第一行两个整数, $n$和$m$, 代表规则数量和需要判断的句子数量.

第二行一个大写字母, 表示乔鲁诺最初拥有的字母.

接下来$n$行, 每行首先是一个大写字母$s_i$, 接下来是一个字符串$t_i$, 表示一个替换规则, 可以将$s_i$替换为$t_i$.

再接下来$m$行, 每行一个小写字符串$S_i$, 代表一个询问.

输出格式

共$m$行, 每行一个数字:

  • 若这个小写字符串不可被生成, 输出-1;
  • 若它可被生成且没有歧义, 输出0;
  • 若它可被生成且有歧义, 输出1.

样例输入1

7 3
A
A BC
B bD
C Dc
B b
B d
C c
D d
bbb
bdc
ddc

样例输出1

-1
1
0

样例解释见题目描述.

样例输入2

10 5
S
S NV
V vcS
V vNP
V vN
V v
N nP
N n
N dn
N dnP
P pN
dnvdnpdn
nvn
nv
nnp
nvcnv

样例输出2

1
0
0
-1
0

注: 这是一个英语的生成规则

dnvdnpdn对应的是The man saw a boy with a telescope.

可以理解为It was a boy with a telescope that the man saw, 也可以理解为It was a boy that the man saw with a telescope.

数据范围和约定

对于所有数据, $n \le 200, m \le 10$, 每个规则生成的结果字符串长度$|t_i|$不超过10, 判断的字符串长度$|S_i|$不超过50.

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!