← 返回题目列表

Codeforces · 172/E

E. BHTML与BCSS

中文机器翻译题面 查看原题

这个问题是关于想象的语言 BHTML 和 BCSS,它们稍微类似于 HTML 和 CSS。仔细阅读问题陈述,因为相似之处相当轻微,并且问题使用了非常简化的类比。

您将获得一个类似于 HTML 但简单得多的 BHTML 文档。它被记录为一系列开始和结束标签。看起来像“<tagname>”的标签称为开始标签,看起来像“</tagname>”的标签称为结束标签。此外,还有一些写为“<tagname/>”的自闭合标签,在这个问题中它们完全等同于“<tagname></tagname>”。此问题中的所有标记名都是由小写拉丁字母组成的字符串,长度为 1 到 10 个字符。不同标签的标签名可以重合。

文档标签构成了正确的括号序列,也就是说,我们可以使用以下操作从给定的序列中获取一个空序列:

- 删除任何自闭合标签“<tagname/>”,
- 删除一对连续(按此顺序)且具有相同名称的开始和结束标记。换句话说,删除子字符串“<tagname></tagname>”。

例如,您可能会收到这样的文档:“<header><p><a/><b></b></p></header><footer></footer>”,但您可能不会收到文档“<a>”、“<a></b>”、“</a><a>”或“<a><b></a></b>”。

显然,对于任何开始标记,都有唯一匹配的结束标记 - 每个这样的对都称为一个元素。自闭合标签也是一个元素。让我们考虑一下,如果第一个元素的标签位于第二个元素的标签之间,则一个元素嵌套在另一个元素内。元素不嵌套于其自身。例如,在上面的示例中,元素“b”嵌套在“header”和“p”中,但它没有嵌套在“a”和“footer”中,也没有嵌套到自身(“b”)。元素“header”嵌套了三个元素,而“footer”则有零个元素。

我们需要 BCSS 规则来在显示 BHTML 文档元素时应用样式。每个规则都记录为单词“x1 x2 ... xn”的子序列。该规则对所有满足列表中两个条件的元素 t 都有效:

- 存在一系列带有标记名“x1”、“x2”、...、“xn”的嵌套元素(即,第二个元素嵌套在第一个元素中,第三个元素嵌套在第二个元素中,依此类推),
- 该序列以元素 t 结束(即元素 t 的标记名等于“xn”)。

例如,如果元素“b”存在嵌套元素“a”,则元素“b”满足规则“a b”的条件。元素“c”满足规则“a b b c”的条件,如果存在三个元素:“a”、“b”、“b”,并且在链“a”-“b”-“b”-“c”中,每个后续元素都嵌套在前一个元素中。

给定一个 BHTML 文档和一组 BCSS 规则,编写一个程序来确定满足每个规则条件的元素数量。

输入

输入的第一行包含一个 BHTML 文档。该文档的长度为 4 到 106 个字符。该文档结构正确,不包含空格或任何其他不必要的字符。标记名由小写拉丁字母组成,长度为 1 到 10 个字符。

第二行包含一个整数 m (1 ≤ m ≤ 200) — 查询数量。然后 m 行包含查询,每行一个。每个查询都是一个序列 x1, x2, ..., xn,其中 xi 是查询的第 i 个元素,n (1 ≤ n ≤ 200) 是查询中的元素数量。元素由单个空格分隔。每个查询不以空格开头也不以空格结尾。每个查询元素是长度从 1 到 10 的小写拉丁字母序列。

输出

打印 m 行,第 j 行应包含与第 j 个 BCSS 规则对应的文档元素的数量。如果根本不存在这样的元素,则在第 0 行打印。

示例

输入 #1

<a><b><b></b></b></a><a><b></b><b><v/></b></a><b></b>
4
a
a b b
a b
b a

输出 #1

2
1
4
0

输入 #2

<b><aa/></b><aa><b/><b/></aa>
5
aa b
b
aa
b aa
a

输出 #2

2
3
2
1
0