← 返回题目列表

Codeforces · 615/C

C. 跑步跑道

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

一个名叫 Ayrat 的男孩生活在 AMI-1511 星球上。这个星球上的每个居民都有天赋。具体来说,Ayrat热爱跑步,而且仅仅跑步对他来说还不够。他梦想让跑步成为一门真正的艺术。

首先,他想用涂层t建造跑道。在 AMI-1511 星球上,轨道的涂层是一系列彩色块,其中每个块都用小英文字母表示。因此,每一个涂层都可以被视为一根绳子。

不幸的是,方块不能自由出售给非商业客户,但 Ayrat 发现了无限数量的涂层。此外,他还有剪刀和胶水。 Ayrat 将购买一些涂层,然后从每个涂层中切出一个连续的部分(子串)并将其粘到轨道涂层的末端。此外,他可能会选择在粘合之前翻转该块。 Ayrat 想知道他需要购买的最少涂层数量才能为他的跑道获得涂层。当然,他也想知道一些方法来获得答案。

输入

输入的第一行包含字符串 s — 商店中存在的涂层。第二行包含字符串 t — Ayrat 想要获得的涂层。两个字符串都非空,仅由小英文字母组成,长度不超过2100。

输出

第一行应包含所需的最小涂层数 n 或 -1(如果无法创建所需的涂层)。

如果答案不是 -1,那么接下来的 n 行应该包含两个整数 xi 和 yi - 相应片段中结束块的数量。如果 xi ≤ yi 则按常规顺序使用该片段,如果 xi > yi 则按相反顺序使用该片段。按照粘合顺序打印这些碎片以获得字符串 t。

示例

输入 #1

abc
cbaabc

输出 #1

2
3 1
1 3

输入 #2

aaabrytaaa
ayrat

输出 #2

3
1 1
6 5
8 7

输入 #3

ami
no

输出 #3

-1

注意

在第一个示例字符串“cbaabc”=“cba”+“abc”中。

在第二个示例中:“ayrat”=“a”+“yr”+“at”。