AT_abc324_c [ABC324C] Error Correction

题目描述

高桥君向青木君发送了一个由小写英文字母组成的字符串 $T$。结果，青木君收到了一个由小写英文字母组成的字符串 $T'$。

$T'$ 可能与 $T$ 有部分不同，具体来说，已知下列 $4$ 种情况中恰好有一种成立：

• $T'$ 与 $T$ 完全相同。
• $T'$ 是在 $T$ 的某一个位置（包括开头和结尾）插入一个小写英文字母后得到的字符串。
• $T'$ 是从 $T$ 中删除某一个字符后得到的字符串。
• $T'$ 是将 $T$ 的某一个字符替换为另一个小写英文字母后得到的字符串。

现在给定青木君收到的字符串 $T'$，以及 $N$ 个由小写英文字母组成的字符串 $S_1, S_2, \ldots, S_N$，请找出所有有可能是高桥君发送的字符串 $T$ 的 $S_i$。

输入格式

输入以如下格式从标准输入读入：

$N$ $T'$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

将所有可能等于 $T$ 的 $S_1, S_2, \ldots, S_N$ 的下标按升序排列，记为 $(i_1, i_2, \ldots, i_K)$。请输出该序列的长度 $K$ 以及该序列本身，格式如下：

$K$ $i_1$ $i_2$ $\ldots$ $i_K$

输入输出样例 #1

输入 #1

5 ababc
ababc
babc
abacbc
abdbc
abbac

输出 #1

4
1 2 3 4

输入输出样例 #2

输入 #2

1 aoki
takahashi

输出 #2

0

输入输出样例 #3

输入 #3

9 atcoder
atoder
atcode
athqcoder
atcoder
tacoder
jttcoder
atoder
atceoder
atcoer

输出 #3

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$

样例解释 1

在 $S_1, S_2, \ldots, S_5$ 中，可能等于 $T$ 的有 $S_1, S_2, S_3, S_4$ 共 $4$ 个，理由如下：

• $S_1$ 可能等于 $T$，因为 $T' = \texttt{ababc}$ 与 $S_1 = \texttt{ababc}$ 完全相同。
• $S_2$ 可能等于 $T$，因为 $T' = \texttt{ababc}$ 可以通过在 $S_2 = \texttt{babc}$ 的开头插入字符 $\texttt{a}$ 得到。
• $S_3$ 可能等于 $T$，因为 $T' = \texttt{ababc}$ 可以通过从 $S_3 = \texttt{abacbc}$ 的第 $4$ 个字符 $\texttt{c}$ 删除得到。
• $S_4$ 可能等于 $T$，因为 $T' = \texttt{ababc}$ 可以通过将 $S_4 = \texttt{abdbc}$ 的第 $3$ 个字符 $\texttt{d}$ 替换为 $\texttt{b}$ 得到。
• $S_5$ 不可能等于 $T$，因为以 $S_5 = \texttt{abbac}$ 作为 $T$ 时，$T' = \texttt{ababc}$ 不满足题目中的 $4$ 个条件中的任何一个。

由 ChatGPT 4.1 翻译