CF1334G Substring Search

给定一个由 $1$ 到 $26$ 的整数构成的排列 $p$（由于是排列，$1$ 到 $26$ 每个整数在 $p$ 中恰好出现一次），以及两个仅包含小写拉丁字母的字符串 $s$ 和 $t$。 如果字符串 $t$ 的某个子串 $t'$ 满足以下条件，则称其为字符串 $s$ 的一次出现： 1. $|t'| = |s|$； 2. 对于每个 $i \in [1, |s|]$，要么 $s_i = t'_i$，要么 $p_{idx(s_i)} = idx(t'_i)$，其中 $idx(c)$ 表示字符 $c$ 在拉丁字母表中的序号（$idx(\text{a}) = 1$，$idx(\text{b}) = 2$，$idx(\text{z}) = 26$）。 例如，若 $p_1 = 2$，$p_2 = 3$，$p_3 = 1$，$s = \text{abc}$，$t = \text{abcaaba}$，则 $t$ 中有三个子串是 $s$ 的出现（分别为 $t' = \text{abc}$，$t' = \text{bca}$ 和 $t' = \text{aba}$）。 请判断 $t$ 的每一个长度为 $|s|$ 的子串是否为 $s$ 的一次出现。

第一行包含 $26$ 个整数 $p_1, p_2, \ldots, p_{26}$（$1 \le p_i \le 26$，且两两不同）。 第二行包含一个字符串 $s$，第三行包含一个字符串 $t$（$2 \le |s| \le |t| \le 2 \times 10^5$），均由小写拉丁字母组成。

输出一个长度为 $|t| - |s| + 1$ 的字符串，每个字符为 $0$ 或 $1$。第 $i$ 个字符为 $1$ 当且仅当 $t$ 的第 $i$ 个字符开始、长度为 $|s|$ 的子串是 $s$ 的一次出现，否则为 $0$。

由 ChatGPT 4.1 翻译