You have a string
s=s1s2...s|s|, where
|s| is the length of string
s, and
si its
i-th character.
Let's introduce several definitions:
-
A substring s[i..j] (1≤i≤j≤|s|) of string s is string sisi+1...sj.
-
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.
Output
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
li ci. Numbers
li ci mean that the prefix of the length
li matches the suffix of length
li and occurs in string
s as a substring
ci times. Print pairs
li ci in the order of increasing li.
给你一个长度为n的长字符串，“完美子串”既是它的前缀也是它的后缀，求“完美子串”的个数且统计这些子串的在长字符串中出现的次数