#x1044. CF432D Prefixes and Suffixes

    ID: 6034 远端评测题 1000ms 256MiB 尝试: 18 已通过: 5 难度: 5 上传者: 标签>CF1800普及+/提高-KMPborder 链前缀出现次数统计失败链接贡献汇总2000

CF432D Prefixes and Suffixes

Prefixes and Suffixes

题面翻译

给你一个长度为n的长字符串,“完美子串”既是它的前缀也是它的后缀,求“完美子串”的个数且统计这些子串的在长字符串中出现的次数

感谢@转身、已陌路 提供的翻译

题目描述

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

Let's introduce several definitions:

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

Your task is, for any prefix of string s s which matches a suffix of string s s , print the number of times it occurs in string s s as a substring.

输入格式

The single line contains a sequence of characters s1s2...s∣s∣ s_{1}s_{2}...s_{|s|} (1<=∣s∣<=105) (1<=|s|<=10^{5}) — string s s . The string only consists of uppercase English letters.

输出格式

In the first line, print integer k k (0<=k<=∣s∣) (0<=k<=|s|) — the number of prefixes that match a suffix of string s s . Next print k k lines, in each line print two integers li l_{i} ci c_{i} . Numbers li l_{i} ci c_{i} mean that the prefix of the length li l_{i} matches the suffix of length li l_{i} and occurs in string s s as a substring ci c_{i} times. Print pairs li l_{i} ci c_{i} in the order of increasing li l_{i} .

样例 #1

样例输入 #1

ABACABA

样例输出 #1

3
1 4
3 2
7 1

样例 #2

样例输入 #2

AAA

样例输出 #2

3
1 3
2 2
3 1