分数: 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是通过改变第三个字符得到的din S_4 =abdbctob. - S_5 不能等于 T,因为如果我们采取 S_5 =
abbacas 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