← 返回题目列表

AtCoder · abc324_c

F. 错误更正

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

高桥发送了一个字符串 T 由小写英文字母组成,写给 Aoki。结果,青木收到了一串字符串 T' 由小写英文字母组成。

T' 可能已更改为 T。具体来说,已知以下四个条件之一成立。

  • T' 等于 T.
  • T' 是在其中一个位置(可能是开头和结尾)插入一个小写英文字母得到的字符串 T.
  • T' 是删除一个字符得到的字符串 T.
  • T' 是改变其中一个字符得到的字符串 T 为另一个小写英文字母。

给你字符串 T' 收到由 Aoki 和 N 字符串 S_1, S_2, \ldots, S_N 由小写英文字母组成。查找其中的所有字符串 S_1, S_2, \ldots, S_N 可能等于字符串 T 由高桥发送。

约束

  • 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.

输入

输入由标准输入按以下格式给出:

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

示例输入 1

5 ababc
ababc
babc
abacbc
abdbc
abbac

示例输出 1

4
1 2 3 4

其中 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 通过插入字母获得 a 开头 删除第四个字符得到 S_2 = babc.
  • S_3 可以等于 T,因为 T' = ababc 删除第四个字符得到 c 来自 S_3 = abacbc.
  • S_4 可以等于 T,因为 T' = ababc 是通过改变第三个字符得到的 d in S_4 = abdbc to b.
  • S_5 不能等于 T,因为如果我们采取 S_5 = abbac as T,那么 T' = ababc 不满足问题陈述中的四个条件中的任何一个。

示例输入 2

1 aoki
takahashi

示例输出 2

0


示例输入 3

9 atcoder
atoder
atcode
athqcoder
atcoder
tacoder
jttcoder
atoder
atceoder
atcoer

示例输出 3

6
1 2 4 7 8 9