← 返回题目列表

Codeforces · 906/E

E. 反转

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

飓风袭击了 Berland 和 Stringsvill 郊区。你要检查一下你最喜欢的琴弦是否合适。 Hurrinace 通过反转一些不相交的子串来打破它。您有一张该字符串在飓风发生前的照片,您希望通过反转其子字符串的最小可能数量将其恢复到原始状态,并找出应反转哪些子字符串。

给您一个字符串 s - 字符串的原始状态和字符串 t - 飓风过后字符串的状态。您应该选择 t 的 k 个不相交的子串,使得这些子串反转后字符串将等于 s 并且 k 是可能的最小值。

输入

输入的第一行包含字符串 s,第二行包含字符串 t。两个字符串具有相同的长度并且由小写英文字母组成。 1≤|s| =|t| ≤5·105

输出

在第一行中打印 k — 应反转的最小子字符串数。接下来输出k行。每行应包含两个整数 li、ri,这意味着您应将子字符串从符号编号 li 反转为符号 ri(字符串以 1 为索引)。这些子字符串不应相交。如果有多个答案,请打印其中一个。如果无法恢复字符串输出-1。

示例

输入 #1

abcxxxdef
cbaxxxfed

输出 #1

2
7 9
1 3