Redirecting to
NADOS

Prefix And Suffix Count

  Prev   Next 
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)
Input Format 
The first line contains string s.
Output Format 
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.
Question Video
Constraints 
1<= s.length() <= 10^5
Sample Input 
ABABABAB
Sample Output 
4
2 4
4 3
6 2
8 1


  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name