← Home
```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

func reverseBytes(a []byte) []byte {
	n := len(a)
	b := make([]byte, n)
	for i := 0; i < n; i++ {
		b[i] = a[n-1-i]
	}
	return b
}

func computeBest(T, U []byte) ([]int, []int) {
	n, m := len(T), len(U)
	best := make([]int, n)
	pos := make([]int, n)
	prev := make([]int, m+1)
	curr := make([]int, m+1)
	for i := n - 1; i >= 0; i-- {
		maxL := 0
		maxPos := 0
		for j := m - 1; j >= 0; j-- {
			if T[i] == U[j] {
				curr[j] = 1 + prev[j+1]
			} else {
				curr[j] = 0
			}
			if curr[j] > maxL {
				maxL = curr[j]
				maxPos = j
			}
		}
		curr[m] = 0
		best[i] = maxL
		pos[i] = maxPos
		prev, curr = curr, prev
	}
	return best, pos
}

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var s, t string
	if _, err := fmt.Fscan(in, &s); err != nil {
		return
	}
	if _, err := fmt.Fscan(in, &t); err != nil {
		return
	}
	sb := []byte(s)
	tb := []byte(t)
	m := len(sb)
	bestF, posF := computeBest(tb, sb)

	sr := reverseBytes(sb)
	bestR, posR := computeBest(tb, sr)

	type pair struct{ x, y int }
	var ans []pair

	i := 0
	for i < len(tb) {
		lF := 0
		pF := 0
		if i < len(bestF) {
			lF = bestF[i]
			pF = posF[i]
		}
		lR := 0
		pR := 0
		if i < len(bestR) {
			lR = bestR[i]
			pR = posR[i]
		}
		if lF == 0 && lR == 0 {
			fmt.Fprintln(out, -1)
			return
		}
		if lF >= lR {
			x := pF + 1
			y := pF + lF
			ans = append(ans, pair{x, y})
			i += lF
		} else {
			L := lR
			r := m - 1 - pR
			l := r - (L - 1)
			x := r + 1
			y := l + 1
			ans = append(ans, pair{x, y})
			i += L
		}
	}

	fmt.Fprintln(out, len(ans))
	for _, p := range ans {
		fmt.Fprintln(out, p.x, p.y)
	}
}
```