题解

思路

对每个查询都要从原串 $s$ 的前缀函数状态出发。若直接沿失配链回退，某个查询的第一个字符可能使失配链长达 $|s|$。因此需要预处理 KMP 自动机。

做法

子任务 1 对每个 $s+t$ 的每个位置枚举所有可能前缀长度，直接比较前缀与后缀。

子任务 2 对每个查询都重新线性计算 $s+t$ 的前缀函数，复杂度 $O(q|s|+\sum|t|)$。

满分做法先计算 $s$ 的前缀函数，并预处理状态 $j<|s|$ 读入每个小写字母后的 KMP 转移。处理查询时，依次追加最多 $10$ 个字符。当失配状态仍在 $s$ 内时直接查自动机；当状态已进入当前查询的追加部分时，因其长度不超过 $10$，直接按前缀函数回退即可。

复杂度

预处理时间为 $O(26|s|)$，每个查询为 $O(|t|^2)$ 的小常数上界，总空间复杂度 $O(26|s|)$。