← 返回题目列表

Codeforces · 432/D

D. 前缀和后缀

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

您有一个字符串 s = s1s2...s|s|,其中 |s|是字符串 s 的长度,si 是第 i 个字符。

我们先介绍几个定义:

- 字符串 s 的子字符串 s[i..j] (1 ≤ i ≤ j ≤ |s|) 是字符串 sisi + 1...sj。
- 长度为 l (1 ≤ l ≤ |s|) 的字符串 s 的前缀是字符串 s[1..l]。
- 长度为 l (1 ≤ l ≤ |s|) 的字符串 s 的后缀是字符串 s[|s| - l + 1..|s|]。

你的任务是,对于与字符串 s 的后缀匹配的字符串 s 的任何前缀,打印它作为子字符串在字符串 s 中出现的次数。

输入

单行包含字符序列 s1s2...s|s| (1 ≤ |s| ≤ 105) — 字符串 s。该字符串仅由大写英文字母组成。

输出

在第一行中,打印整数 k (0 ≤ k ≤ |s|) — 与字符串 s 的后缀匹配的前缀数量。接下来打印k行,每行打印两个整数li ci。数字li ci 表示长度为li 的前缀与长度为li 的后缀匹配,并作为子串ci 出现在字符串s 中。按 li 递增的顺序打印 li ci 对。

示例

输入 #1

ABACABA

输出 #1

3
1 4
3 2
7 1

输入 #2

AAA

输出 #2

3
1 3
2 2
3 1