CF1334G.Substring Search

You are given a permutation $p$ consisting of exactly $26$ integers from $1$ to $26$ (since it is a permutation, each integer from $1$ to $26$ occurs in $p$ exactly once) and two strings $s$ and $t$ consisting of lowercase Latin letters.

A substring $t'$ of string $t$ is an occurence of string $s$ if the following conditions are met:

1. $|t'| = |s|$;
2. for each $i \in [1, |s|]$, either $s_i = t'_i$, or $p_{idx(s_i)} = idx(t'_i)$, where $idx(c)$ is the index of character $c$ in Latin alphabet ($idx(\text{a}) = 1$, $idx(\text{b}) = 2$, $idx(\text{z}) = 26$).

For example, if $p_1 = 2$, $p_2 = 3$, $p_3 = 1$, $s = \text{abc}$, $t = \text{abcaaba}$, then three substrings of $t$ are occurences of $s$ (they are $t' = \text{abc}$, $t' = \text{bca}$ and $t' = \text{aba}$).

For each substring of $t$ having length equal to $|s|$, check if it is an occurence of $s$.

给你一个由 $1$ 到 $26$ 的整数构成的排列 $p$（由于是排列，$1$ 到 $26$ 中的每个整数在 $p$ 中恰好出现一次），以及两个仅包含小写拉丁字母的字符串 $s$ 和 $t$。

字符串 $t$ 的一个子串 $t'$ 被称为字符串 $s$ 的一个出现（occurrence），当且仅当满足以下条件：

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|$ 的子串是 $s$ 的出现（它们分别是 $t' = \text{abc}$、$t' = \text{bca}$ 和 $t' = \text{aba}$）。

对 $t$ 的每一个长度等于 $|s|$ 的子串，判断其是否为 $s$ 的一个出现。

The first line contains $26$ integers $p_1$, $p_2$, ..., $p_{26}$ ($1 \le p_i \le 26$, all these integers are pairwise distinct).

The second line contains one string $s$, and the third line contains one string $t$ ($2 \le |s| \le |t| \le 2 \cdot 10^5$) both consisting of lowercase Latin letters.

第一行包含 $26$ 个整数 $p_1$, $p_2$, ..., $p_{26}$（$1 \le p_i \le 26$，且这些整数两两互不相同）。

第二行包含一个字符串 $s$，第三行包含一个字符串 $t$（$2 \le |s| \le |t| \le 2 \cdot 10^5$），二者均由小写拉丁字母组成。

Print a string of $|t| - |s| + 1$ characters, each character should be either 0 or 1. The $i$-th character should be 1 if and only if the substring of $t$ starting with the $i$-th character and ending with the $(i + |s| - 1)$-th character (inclusive) is an occurence of $s$.

输出一个长度为 $|t| - |s| + 1$ 的字符串，其中每个字符只能是 0 或 1。当且仅当 $t$ 中从第 $i$ 个字符开始、到第 $(i + |s| - 1)$ 个字符（含）结束的子串等于 $s$ 时，该字符串的第 $i$ 个字符为 1。