#P10486. [入门赛 #25] sql

[入门赛 #25] sql

题目背景

sql 是一种强大的数据库查询语言。在本题中,你需要实现一个部分功能的 sql 解析器。

题目描述

一个数据库可以看作若干张二维表的合集。

例如,一个学生信息管理系统的数据库可能会有如下两张二维表:

basic_info

name sid grade
Fusu 001 1
Maxmilite 002 2
Expect2004 003

GPA:

sid GPA
001 77.88
002 99.9
003 99.7

上述表的第一行称作表头,接下来每一行表示表的一组信息。例如,basic_info 的第二行表示存在一名学生的姓名(name)是 Fusu\texttt{Fusu},学号 (sid) 为 001\texttt{001},年级(grade)为 1\texttt{1}

一个正式的 sql 语言应该支持跨表查询,但是在本题中,你只需要支持在单个表内的查询。我们认为表内的一切属性都以字符串的形式给出。

你需要支持如下格式的查询语句:

select [columns] from [table_name] where [header]=x

上式中,columns 是若干个表头table_name表名header表头xx 是给出的条件。它表示在 table_name 这个表里查询 header 这一列为 xx 的所有行的所有 columns 列里的信息。

例如,如果对上述例子里的表执行如下语句:

select name from basic_info where grade=1

表示在 basic_info 表里查询 grade 列为 11 的所有行,并输出它们的 name 列,因此结果为:

Fusu

如果执行

select name,sid,grade from basic_info where grade=2

那么就找到 basic_info 表里所有 grade2 的行,并依次输出它们的 namesidgrade。结果为:

Maxmilite 002 2
Expect2004 003 2

可以看到,select 语句的第一组参数 columns 可以是多个表头名称,此时应该按照 columns 给出的顺序输出每个对应的列信息。通过 where 后面的条件可以查询到多行满足要求的行时,应按照表的输入顺序(即从上到下)输出每行要求的信息。

你需要实现这个 sql 语句解析器,给出 sql 查询结果。注意,我们保证了在查询语句里表名只有一个,且 where 后面的条件有且仅有一个等式。

输入格式

输入的第一行是一个整数 nn,表示数据库中表的个数。

接下来依次给出每张表的信息:
第一行是一个字符串 table_name,表示表的名称。
第二行有两个整数 x,yx,y,表示这张表的大小为 xxyy 列。 第三行有 yy 个字符串,表示这张表的表头。 接下来 x1x - 1 行,每行 yy 个字符串,给出这张表上每一行的信息。

接下来是一个整数 mm,表示 sql 语句的数量。

接下来 mm 行,每行一个 sql 语句,格式一定是

select [columns] from [table_name] where [header]=x

保证 columnstable_nameheaderx 这四个参数内部没有空格。

数据保证查询语句合法,即 columnstable_nameheader 这三个参数所提供的表头、表名都是存在的,且给出的查询条件一定能找到至少一行符合,即查询结果非空。

保证 columns 里没有重复的表头名。

输出格式

对于每个查询,输出若干行,依次表示查询结果。

一行查询结果里,如果有若干个列的信息要输出,输出字符串之间用一个空格隔开。

1
basic_info
4 3
name sid grade
Fusu 001 1
Maxmilite 002 2
Expect2004 003 2
2
select name from basic_info where grade=1
select sid,name from basic_info where grade=2

Fusu
002 Maxmilite
003 Expect2004

2
basic_info
4 3
name sid grade
Fusu 001 1
Maxmilite 002 2
Expect2004 003 2
GPA
2 2
sid GPA
001 77.88
1
select GPA from GPA where sid=001

77.88

2
show_corner
3 2
h1 h2
1 2
1 2
show_corner2
3 1
h0
1
1
2
select h1,h2 from show_corner where h1=1
select h0 from show_corner2 where h0=1

1 2
1 2
1
1

提示

样例 3 解释

输入的表单可能有若干行是重复的,你无需对这些行做特殊处理,可以认为它们是不同的。每次查询需要输出所有符合要求的行。例如,在第一条 sql 中,1 2 这一行出现了两次且符合要求,因此输出了两次 1 2

数据规模与约定

测试点编号 表的数量为 11 表头数量为 1 columns 里仅有一列表头
1, 2 \checkmark \checkmark \checkmark
3, 4 ×\times
5, 6 ×\times \checkmark
7, 8 ×\times
9, 10 ×\times

对全部的测试数据,保证:

  • 1n101 \leq n \leq 10
  • 1x1001 \leq x\leq 1001y101 \leq y \leq 10
  • 1m10001 \leq m \leq 1000
  • 表头 table_name 长度不超过 100100
  • 表的内容和表头的字符串长度不超过 1010columns 的长度不超过 100100
  • 除了 columns 信息以外,输入的字符串均不含有逗号 ,
  • 输入字符串均为可见字符,ASCII 范围为 3212632\sim 126(含两端),且不含符号 =

提示

请注意大量数据输出对程序效率造成的影响,选择合适的输出方式,避免超时。