A9551. Prefixes and Suffixes

You have a string $s=s_{1}s_{2}...s_{|s|}$ , where $|s|$ is the length of string $s$ , and $s_{i}$ its $i$ -th character.

Let's introduce several definitions:

- A substring $s[i..j]$ $(1<=i<=j<=|s|)$ of string $s$ is string $s_{i}s_{i+1}...s_{j}$ .
- The prefix of string $s$ of length $l$ $(1<=l<=|s|)$ is string $s[1..l]$ .
- The suffix of string $s$ of length $l$ $(1<=l<=|s|)$ is string $s[|s|-l+1..|s|]$ .

Your task is, for any prefix of string $s$ which matches a suffix of string $s$ , print the number of times it occurs in string $s$ as a substring.
您有一个字符串 s = s1s2...s|s| ，其中 |s| 是字符串 s 的长度，而 si 是其第 i 个字符。

下面我们来介绍几个定义：

子串 s[i..j] 字符串 s 的子串 (1 ≤ i ≤ j ≤ |s|) 是字符串 $s_i s_{i + 1}...sj$。
长度为 l 的字符串 s 的前缀 (1 ≤ l ≤ |s|) 是字符串 $s_i s_{i + 1}...sj$ 。 (1 ≤ l ≤ |s|) 的前缀是字符串 s[1..l] 。
长度为 l 的字符串 s 的后缀是字符串 s[1..l] 。 (1 ≤ l ≤ |s|) 的后缀是字符串 s[|s| - l + 1..|s|] 。
您的任务是，对于字符串 s 中与字符串 s 的后缀匹配的任何前缀，打印它作为子串在字符串 s 中出现的次数。

The single line contains a sequence of characters $s_{1}s_{2}...s_{|s|}$ $(1<=|s|<=10^{5})$ — string $s$ . The string only consists of uppercase English letters.
输入
单行包含一个字符序列 $s_{1}s_{2}...s_{|s|}$ $(1<=|s|<=10^{5})$- 字符串 s 。字符串只包含大写英文字母。

In the first line, print integer $k$ $(0<=k<=|s|)$ — the number of prefixes that match a suffix of string $s$ . Next print $k$ lines, in each line print two integers $l_{i}$ $c_{i}$ . Numbers $l_{i}$ $c_{i}$ mean that the prefix of the length $l_{i}$ matches the suffix of length $l_{i}$ and occurs in string $s$ as a substring $c_{i}$ times. Print pairs $l_{i}$ $c_{i}$ in the order of increasing $l_{i}$ .
输出
第一行，打印整数 k (0 ≤ k ≤ |s|) - 匹配字符串 s 后缀的前缀数。 (0 ≤ k ≤ |s|) - 匹配字符串 s 后缀的前缀数。接下来打印 k 行，每行打印两个整数 li ci 。 ci .数字 li ci 表示长度为 li 的前缀与长度为 li 的后缀相匹配，并且作为子串 ci 出现在字符串 s 中的次数为 ci 。打印字符对 li ci 依次递增 li 。