A15312 | Prefix Function Queries

You are given a string $s$ , consisting of lowercase Latin letters.

You are asked $q$ queries about it: given another string $t$ , consisting of lowercase Latin letters, perform the following steps:

1. concatenate $s$ and $t$ ;
2. calculate the prefix function of the resulting string $s+t$ ;
3. print the values of the prefix function on positions $|s|+1, |s|+2, \dots, |s|+|t|$ ( $|s|$ and $|t|$ denote the lengths of strings $s$ and $t$ , respectively);
4. revert the string back to $s$ .

The prefix function of a string $a$ is a sequence $p_1, p_2, \dots, p_{|a|}$ , where $p_i$ is the maximum value of $k$ such that $k < i$ and $a[1..k]=a[i-k+1..i]$ ( $a[l..r]$ denotes a contiguous substring of a string $a$ from a position $l$ to a position $r$ , inclusive). In other words, it's the longest proper prefix of the string $a[1..i]$ that is equal to its suffix of the same length.
给你一个由小写拉丁字母组成的字符串 $s$ 。

向您提出有关它的 $q$ 个问题：给您另一个由小写拉丁字母组成的字符串 $t$ ，请执行以下步骤：

1. 连接 $s$ 和 $t$ ；
2. 计算得到的字符串 $s+t$ 的前缀函数；
3. 在位置 $|s|+1, |s|+2, \dots, |s|+|t|$ 上打印前缀函数值（ $|s|$ 和 $|t|$ 分别表示字符串 $s$ 和 $t$ 的长度）；
4. 将字符串还原为 $s$ 。

字符串 $a$ 的前缀函数是一个序列 $p_1, p_2, \dots, p_{|a|}$ ，其中 $p_i$ 是 $k$ 的最大值，而 $k < i$ 和 $a[1..k]=a[i-k+1..i]$ 是 $k$ 的最大值。 $a[l..r]$ 表示字符串 $a$ 从位置 $l$ 到位置 $r$ （含）的连续子串）。换句话说，它是字符串 $a[1..i]$ 的最长适当前缀，等于其相同长度的后缀。

The first line contains a non-empty string $s$ ( $1 \le |s| \le 10^6$ ), consisting of lowercase Latin letters.

The second line contains a single integer $q$ ( $1 \le q \le 10^5$ ) — the number of queries.

Each of the next $q$ lines contains a query: a non-empty string $t$ ( $1 \le |t| \le 10$ ), consisting of lowercase Latin letters.
输入

第一行包含一个非空字符串 $s$ ( $1 \le |s| \le 10^6$ )，由小写拉丁字母组成。

第二行包含一个整数 $q$ ( $1 \le q \le 10^5$ ) - 查询次数。

接下来的每行 $q$ 都包含一个查询：一个由小写拉丁字母组成的非空字符串 $t$ ( $1 \le |t| \le 10$ )。

For each query, print the values of the prefix function of a string $s+t$ on positions $|s|+1, |s|+2, \dots, |s|+|t|$ .
输出

针对每个查询，打印位置 $|s|+1, |s|+2, \dots, |s|+|t|$ 上字符串 $s+t$ 的前缀函数值。