Prefixes and Suffixes

题意翻译

给你一个长度为n的长字符串，“完美子串”既是它的前缀也是它的后缀，求“完美子串”的个数且统计这些子串的在长字符串中出现的次数 感谢@转身、已陌路 提供的翻译

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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} $ .

输入输出样例

输入样例 #1

ABACABA

输出样例 #1

3
1 4
3 2
7 1

输入样例 #2

AAA

输出样例 #2

3
1 3
2 2
3 1