Prefix And Suffix Count
hard
Given a string 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. Expected Complexity: O(n)
Constraints
1<= s.length() <= 10^5
Format
Input
The first line contains string s.
Output
In the first line, print integer k (0
Example
Sample Input
ABABABAB
Sample Output
4
2 4
4 3
6 2
8 1
Question Video