Running Track

题意翻译

### 题意 给定两个字符串 $s,t$，每次可以从 $s$ 中选取一段连续的子串（每次取对下次没有影响），该子串可以进行翻转，问最少取多少次子串可以组合出$s$。如果不存在方案，输出-1；否则输出最少次数及方案。 输出方案 $l,r$ 时，如果选取 $[l,r]$ 的子串且不进行翻转，则输出 $l,r$ ；如果选取 $[l,r]$ 的子串且进行翻转，则输出 $r,l$ 。

题目描述

A boy named Ayrat lives on planet AMI-1511. Each inhabitant of this planet has a talent. Specifically, Ayrat loves running, moreover, just running is not enough for him. He is dreaming of making running a real art. First, he wants to construct the running track with coating $ t $ . On planet AMI-1511 the coating of the track is the sequence of colored blocks, where each block is denoted as the small English letter. Therefore, every coating can be treated as a string. Unfortunately, blocks aren't freely sold to non-business customers, but Ayrat found an infinite number of coatings $ s $ . Also, he has scissors and glue. Ayrat is going to buy some coatings $ s $ , then cut out from each of them exactly one continuous piece (substring) and glue it to the end of his track coating. Moreover, he may choose to flip this block before glueing it. Ayrat want's to know the minimum number of coating $ s $ he needs to buy in order to get the coating $ t $ for his running track. Of course, he also want's to know some way to achieve the answer.

输入输出格式

输入格式

First line of the input contains the string $ s $ — the coating that is present in the shop. Second line contains the string $ t $ — the coating Ayrat wants to obtain. Both strings are non-empty, consist of only small English letters and their length doesn't exceed $ 2100 $ .

输出格式

The first line should contain the minimum needed number of coatings $ n $ or -1 if it's impossible to create the desired coating. If the answer is not -1, then the following $ n $ lines should contain two integers $ x_{i} $ and $ y_{i} $ — numbers of ending blocks in the corresponding piece. If $ x_{i}<=y_{i} $ then this piece is used in the regular order, and if $ x_{i}&gt;y_{i} $ piece is used in the reversed order. Print the pieces in the order they should be glued to get the string $ 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

说明

In the first sample string "cbaabc" = "cba" + "abc". In the second sample: "ayrat" = "a" + "yr" + "at".