CF615C Running Track

一个名叫 Ayrat 的男孩生活在 AMI-1511 星球上。这个星球上的每个居民都有一种天赋。具体来说，Ayrat 热爱跑步，而且对他来说仅仅跑步还不够。他梦想着让跑步成为一门真正的艺术。 首先，他想要建造一条有特殊涂层 $t$ 的跑道。在 AMI-1511 星球上，跑道的涂层是一串有颜色的方块，每个方块用一个小写英文字母表示。因此，每种涂层都可以看作一个字符串。 不幸的是，普通消费者无法随意购买方块，但 Ayrat 发现商店里有无限数量的某种涂层 $s$。他还拥有剪刀和胶水。Ayrat 打算购买若干条涂层 $s$，然后从每条涂层中裁剪出**恰好一个**连续片段（即子串），将它们依次粘贴到跑道的末尾。此外，他还可以选择将这个片段翻转后再粘贴。Ayrat 想知道，为了获得目标涂层 $t$，他最少需要购买多少条涂层 $s$。当然，他还想知道实现方案的一种方式。

输入的第一行包含字符串 $s$，即商店中可购得的涂层。第二行包含字符串 $t$，即 Ayrat 想要获得的跑道涂层。两个字符串均非空，仅包含小写英文字母，且长度不超过 $2100$。

第一行输出最少所需购买涂层 $s$ 的数量 $n$，如果无法获得目标涂层则输出 $-1$。 如果答案不是 $-1$，接下来的 $n$ 行，每行输出两个整数 $x_i$ 和 $y_i$，表示每块片段在涂层 $s$ 中的结尾方块的位置编号。如果 $x_i \leq y_i$，表示该片段以正常顺序使用；如果 $x_i > y_i$，表示该片段以翻转顺序使用。按这些片段粘贴的顺序能得到字符串 $t$。

在第一个样例中，字符串 "cbaabc" = "cba" + "abc"。 在第二个样例中："ayrat" = "a" + "yr" + "at"。 由 ChatGPT 5 翻译