← 返回题目列表

Codeforces · 235/C

C. 循环任务

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

前几天,WJMZBMR 学会了如何通过预处理字符串 s 来快速回答“字符串 x 在字符串 s 中出现了多少次”的查询。但现在他想让事情变得更难。

所以他想问“s中有多少个连续子串与给定的字符串x循环同构”。给定字符串 s 和 n 个字符串 xi,对于每个字符串 xi 求出 s 中有多少个连续子串与 xi 循环同构。

如果两个字符串可以旋转一个字符串以获得另一个字符串,则称为循环同构。这里的“旋转”意味着“从字符串的开头取出一些连续的字符(可能没有),并以相同的顺序将它们放回字符串的末尾”。例如,字符串“abcde”可以旋转为字符串“deabc”。我们可以从开头取出字符“abc”并将它们放在“de”的末尾。

输入

第一行包含一个非空字符串 s。字符串 s 的长度不大于 106 个字符。

第二行包含一个整数 n (1 ≤ n ≤ 105) — 查询数量。然后是 n 行:第 i 行包含字符串 xi — 第 i 个查询的字符串。 xi 的总长度小于或等于 106 个字符。

在这个问题中,字符串仅由小写英文字母组成。

输出

对于每个查询 xi 打印一个整数,该整数显示 s 中有多少个连续子串与 xi 循环同构。按照输入中给出的顺序打印查询的答案。

示例

输入 #1

baabaabaaa
5
a
ba
baa
aabaa
aaba

输出 #1

7
5
7
3
5

输入 #2

aabbaa
3
aa
aabb
abba

输出 #2

2
3
3