← 返回题目列表

Codeforces · 212/B

B. Polycarpus 正在寻找好的子字符串

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

我们将字符串 s[a, b] = sasa + 1... sb (1 ≤ a ≤ b ≤ |s|) 称为字符串 s = s1s2... s|s| 的子字符串,其中 |s|是字符串 s 的长度。

非空字符串 t 的踪迹是该字符串组成的一组字符。例如,字符串“aab”的踪迹等于{'a', 'b'}。

让我们考虑一个任意字符串 s 及其踪迹等于 C 的子串集合。我们将通过包含 r(C, s) 来表示该集合中最大子串的数量。属于某个集合的长度为 n = b - a + 1 的子串 s[a, b] 称为包含最大子串,如果该集合中不存在长度大于 n 的子串 s[x, y],使得 1 ≤ x ≤ a ≤ b ≤ y ≤ |s|。字符串 s 的两个子串即使相等但位于 s 的不同位置,也被认为是不同的。

Polycarpus 在弦乐考试中遇到了一项具有挑战性的实践任务。他必须执行以下操作:给定字符串 s 和非空字符集 C1, C2, ..., Cm,找到每个集合 Ci 的 r(Ci, s)。帮助波利卡普斯解决问题,因为他真的不想被大学开除并去参军!

输入

第一行包含一个非空字符串 s (1 ≤ |s| ≤ 106)。

第二行包含一个整数 m (1 ≤ m ≤ 104)。接下来的 m 行包含集合 Ci 的描述。第 i 行包含字符串 ci,其踪迹等于 Ci。保证每个字符串ci的所有字符都不同。

请注意,Ci 不一定不同。所有给定的字符串均由小写英文字母组成。

输出

打印 m 个整数 — 第 i 个整数必须等于 r(Ci, s)。

示例

输入 #1

aaaaa
2
a
a

输出 #1

1
1

输入 #2

abacaba
3
ac
ba
a

输出 #2

1
2
4