#P4503. 两个串

    ID: 3740 传统题 1000ms 256MiB 尝试: 1631 已通过: 408 难度: 5 上传者: 标签>难度分类普及+/提高-位运算位集加速字符串匹配位集求交CF1800bitset

两个串

两个串

题目描述

兔子们在玩两个串的游戏。给定两个字符串 SS 和 TT,兔子们想知道 TT 在 SS 中出现了几次,分别在哪些位置出现。

TT 中的 ? 匹配 SS 中的任意一个字符。匹配要求 TT 中的每个非通配符与对应字符相同,匹配的位置可以重叠。

输入格式

两行两个字符串,分别代表 SS 和 TT。

输出格式

第一行输出非负整数 kk,表示 TT 在 SS 中匹配的次数。

接下来 kk 行,每行输出一个匹配的起始下标,按从小到大的顺序排列。SS 的下标从 00 开始。

样例

bbabaababaaaaabaaaaaaaabaaabbbabaaabbabaabbbbabbbbbbabbaabbbababababbbbbbaaabaaabbbbbaabbbaabbbbabab
a?aba?abba
0

数据规模与约定

1≤∣T∣≤∣S∣≤1051\le |T|\le |S|\le 10^5。SS 只包含小写英文字母,TT 只包含小写英文字母及 ?。