Error Correction

题目描述

Takahashi 发送了一个由小写英文字母构成的字符串 $T$ 给 Aoki。结果，Aoki 收到的字符串为 $T'$，它也由小写英文字母构成。 $T'$ 可能与 $T$ 不同。具体来说，已知恰好满足以下四个条件中的一个。

$T'$ 等于 $T$。 $T'$ 是通过在 $T$ 的某个位置（可能是开头或结尾）插入一个小写英文字母得到的字符串。 $T'$ 是通过从 $T$ 中删除一个字符得到的字符串。 $T'$ 是通过将 $T$ 中的某个字符改为另一个小写英文字母得到的字符串。

给出 Aoki 收到的字符串 $T'$ 和 $N$ 个由小写英文字母构成的字符串 $S_1, S_2, \ldots, S_N$。找出在 $S_1, S_2, \ldots, S_N$ 中所有可能等于 Takahashi 发送的字符串 $T$ 的字符串。

输入格式

输入由标准输入给出，格式如下： $N$ $T'$ $S_1$ $S_2$ $\vdots$ $S_N$

输出格式

设 $(i_1, i_2, \ldots, i_K)$ 为在 $S_1, S_2, \ldots, S_N$ 中所有可能等于 $T$ 的字符串的下标序列，按升序排列。 以以下格式输出该序列的长度 $K$ 和该序列： $K$ $i_1$ $i_2$ $\ldots$ $i_K$

5 ababc
ababc
babc
abacbc
abdbc
abbac

4
1 2 3 4

1 aoki
takahashi

0

9 atcoder
atoder
atcode
athqcoder
atcoder
tacoder
jttcoder
atoder
atceoder
atcoer

6
1 2 4 7 8 9

提示

$N$ 是一个整数。 $1 \leq N \leq 5 \times 10^5$ $S_i$ 和 $T'$ 的长度在 $1$ 到 $5 \times 10^5$（含）之间，且由小写英文字母构成。 $S_1, S_2, \ldots, S_N$ 的总长度最多为 $5 \times 10^5$。在 $S_1, S_2, \ldots, S_5$ 中，可能等于 $T$ 的字符串是 $S_1, S_2, S_3, S_4$，解释如下。

$S_1$ 可能等于 $T$，因为 $T' =$ $ababc$ 等于 $S_1 =$ $ababc$。 $S_2$ 可能等于 $T$，因为 $T' =$ $ababc$ 是通过在 $S_2 =$ $babc$ 的开头插入字母 $a$ 得到的。 $S_3$ 可能等于 $T$，因为 $T' =$ $ababc$ 是通过从 $S_3 =$ $abacbc$ 中删除第 4 个字符 $c$ 得到的。 $S_4$ 可能等于 $T$，因为 $T' =$ $ababc$ 是通过将 $S_4 =$ $abdbc$ 的第 3 个字符 $d$ 改为 $b$ 得到的。 $S_5$ 不可能等于 $T$，因为 若取 $S_5 =$ $abbac$ 作为 $T$，则 $T' =$ $ababc$ 不满足题目陈述中的任何一个条件。

标签: AtCoder|abc324C

来源

AtCoder|abc324C