CF235C Cyclical Quest

几天前，WJMZBMR 学会了通过预处理字符串 $s$，快速回答“字符串 $x$ 在字符串 $s$ 中出现了多少次”这个查询。但现在他想让这个问题变得更加困难。 于是他提出了这样一个问题：“字符串 $s$ 有多少个连续子串与给定字符串 $x$ 是循环同构的？”给定字符串 $s$ 和 $n$ 个字符串 $x_i$，对于每一个字符串 $x_i$，请你计算有多少个 $s$ 的连续子串与 $x_i$ 是循环同构的。 当一个字符串能够通过旋转操作变为另一个字符串时，这两个字符串被称为循环同构。这里的“旋转”指的是：把字符串开头一段连续的字符（可以为空）移动到字符串末尾，并保持顺序。例如，字符串 "abcde" 可以旋转成 "deabc"；我们可以把开头的 "abc" 放到末尾 "de" 之后。

第一行包含一个非空字符串 $s$，字符串 $s$ 的长度不超过 $10^6$ 个字符。 第二行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示询问的个数。接下来的 $n$ 行，每行包含一个字符串 $x_i$，即第 $i$ 个询问。所有 $x_i$ 的总长度不超过 $10^6$ 个字符。 本题中的字符串均由小写英文字母组成。

对于每个询问 $x_i$，输出一个整数，表示 $s$ 的连续子串中有多少个与 $x_i$ 循环同构的子串。答案按输入顺序输出。

由 ChatGPT 5 翻译