seuOJ295 - 加 密 通 话

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：春季, 夏季, 校赛, 2020

题目描述

众所周知，大司老师非常擅长加密通话，现小法司得到两个字符串 $s$ 和 $t$，它们的长度分别为 $n, m$。

已知大司老师可能将 $t$ 中某些字符进行更换，而小法司已经拿到了大司老师关于 $26$ 个字母的替换规则表 $a$，小法司想找到所以满足如下条件的 $s$ 的子串 $s'$：

1. $|t| = |s'|$。
2. $\forall i \in [1, m]$, $s'_i = t_i$ 或者 $s'_i$ 可以替换为 $t_i$。

(如 $x$ 为一个字符串，我们记 $x_i$ 为 $x$ 中的第 $i$ 个字符。)

注：每种字符在满足替换条件的前提下在整个匹配过程中可以替换为不同的其他字符，如 aaa 可以替换为 bcd(前提是 a 能替换为 b/c/d)。

小法司想找到所有这样的子串 $s'$。

输入格式

第一行有两个整数 $n, m(1 \leq n, m \leq 10^5)$，表示字符串 $s$ 和 $t$ 的长度。

接下来两行分别表示两个字符串 $s,t$, 字符串中的所有字符都是英文小写字母。

接下来输入一个 $26\times 26$ 的矩阵 $a$，$a_{ij} = 1$ 表示 $i$ 代表的字符可以替换为 $j$ 代表的字符($1$ 代表字符 a, $2$ 代表字符 b，$3$ 代表字符 c $\ldots$ $26$ 代表字符z)，而 $a_{ij} = 0$ 表示不能进行这样的替换。

输入数据保证 $a_{ii} = 1$。

输出格式

输出一个长度为 $n - m + 1$ 的字符串，其中第 $i$ 位为 $1$ 表示以第 $i$ 位为起始长度为 $m$ 的子串 $s'$ 能与 $t$ 匹配上，第 $i$ 位为 $0$ 则表示不能。

样例

样例输入

6 3
abcabc
abc
10000000000000000000000000
01000000000000000000000000
00100000000000000000000000
00010000000000000000000000
00001000000000000000000000
00000100000000000000000000
00000010000000000000000000
00000001000000000000000000
00000000100000000000000000
00000000010000000000000000
00000000001000000000000000
00000000000100000000000000
00000000000010000000000000
00000000000001000000000000
00000000000000100000000000
00000000000000010000000000
00000000000000001000000000
00000000000000000100000000
00000000000000000010000000
00000000000000000001000000
00000000000000000000100000
00000000000000000000010000
00000000000000000000001000
00000000000000000000000100
00000000000000000000000010
00000000000000000000000001

样例输出

1001