CF1721E Prefix Function Queries

给定一个由小写拉丁字母组成的字符串 $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]$（$a[l..r]$ 表示字符串 $a$ 从第 $l$ 个字符到第 $r$ 个字符的连续子串，包含两端）。换句话说，就是 $a[1..i]$ 的最长真前缀，且该前缀等于其后缀。

第一行包含一个非空字符串 $s$（$1 \le |s| \le 10^6$），由小写拉丁字母组成。 第二行包含一个整数 $q$（$1 \le q \le 10^5$），表示询问的数量。 接下来的 $q$ 行，每行包含一个非空字符串 $t$（$1 \le |t| \le 10$），由小写拉丁字母组成。

对于每个询问，输出字符串 $s+t$ 的前缀函数在位置 $|s|+1, |s|+2, \dots, |s|+|t|$ 上的值。

由 ChatGPT 4.1 翻译