← Home
```go
package main

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

const LOG = 17
const B1 uint64 = 911382323
const B2 uint64 = 972663749

var (
	s    []byte
	ch   []byte
	nxt  []int32
	lns  []int32
	ans  []int32
	up   [LOG][]int32
	h1   [LOG][]uint64
	h2   [LOG][]uint64
	pow1 []uint64
	pow2 []uint64
)

func build(u int32, c byte, nx int32) {
	ui := int(u)
	ch[ui] = c
	nxt[ui] = nx
	lns[ui] = lns[int(nx)] + 1
	up[0][ui] = nx
	v := uint64(c-'a') + 1
	h1[0][ui] = v
	h2[0][ui] = v
	for k := 1; k < LOG; k++ {
		if int(lns[ui]) >= 1<<k {
			mid := up[k-1][ui]
			mi := int(mid)
			up[k][ui] = up[k-1][mi]
			h1[k][ui] = h1[k-1][ui]*pow1[1<<(k-1)] + h1[k-1][mi]
			h2[k][ui] = h2[k-1][ui]*pow2[1<<(k-1)] + h2[k-1][mi]
		}
	}
}

func cmp(a, b int32) int {
	if a == b {
		return 0
	}
	x, y := a, b
	for k := LOG - 1; k >= 0; k-- {
		if int(lns[int(x)]) >= 1<<k && int(lns[int(y)]) >= 1<<k &&
			h1[k][int(x)] == h1[k][int(y)] &&
			h2[k][int(x)] == h2[k][int(y)] {
			x = up[k][int(x)]
			y = up[k][int(y)]
		}
	}
	if x == 0 {
		if y == 0 {
			return 0
		}
		return -1
	}
	if y == 0 {
		return 1
	}
	if ch[int(x)] < ch[int(y)] {
		return -1
	}
	return 1
}

func jump(u int32, d int32) int32 {
	x := u
	rem := int(d)
	for k := LOG - 1; k >= 0; k-- {
		if rem >= 1<<k {
			x = up[k][int(x)]
			rem -= 1 << k
		}
	}
	return x
}

func collect(u int32, k int) string {
	buf := make([]byte, 0, k)
	x := u
	for k > 0 && x != 0 {
		buf = append(buf, ch[int(x)])
		x = nxt[int(x)]
		k--
	}
	return string(buf)
}

func lastK(u int32, k int) string {
	start := jump(u, lns[int(u)]-int32(k))
	return collect(start, k)
}

func main() {
	in := bufio.NewReaderSize(os.Stdin, 1<<20)
	var str string
	fmt.Fscan(in, &str)
	s = []byte(str)
	n := len(s)

	ch = make([]byte, n+1)
	nxt = make([]int32, n+1)
	lns = make([]int32, n+1)
	ans = make([]int32, n+2)
	pow1 = make([]uint64, n+1)
	pow2 = make([]uint64, n+1)

	pow1[0], pow2[0] = 1, 1
	for i := 0; i < n; i++ {
		pow1[i+1] = pow1[i] * B1
		pow2[i+1] = pow2[i] * B2
	}

	for k := 0; k < LOG; k++ {
		up[k] = make([]int32, n+1)
		h1[k] = make([]uint64, n+1)
		h2[k] = make([]uint64, n+1)
	}

	for i := n - 1; i >= 0; i-- {
		u := int32(i + 1)
		build(u, s[i], ans[i+1])
		if i+1 < n && s[i] == s[i+1] {
			if cmp(u, ans[i+2]) <= 0 {
				ans[i] = u
			} else {
				ans[i] = ans[i+2]
			}
		} else {
			ans[i] = u
		}
	}

	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	for i := 0; i < n; i++ {
		u := ans[i]
		l := int(lns[int(u)])
		if l == 0 {
			out.WriteString("0\n")
			continue
		}
		var res string
		if l <= 10 {
			res = collect(u, l)
		} else {
			res = collect(u, 5) + "..." + lastK(u, 2)
		}
		out.WriteString(strconv.Itoa(l))
		out.WriteByte(' ')
		out.WriteString(res)
		out.WriteByte('\n')
	}
}
```