Given a string consisting of lowercase English alphabets of length N
Consider each proper prefix of length from 1 to N-1 and compare that prefix with each of the other same-length substrings lexicographically except the prefix itself.
For each prefix of length from 1 to N-1 ,compare that prefix with each of the same length substrings, and determine how many substrings are greater, equal, and smaller than that prefix respectively.
Notes A substring is a contiguous sequence of characters within a string .For example the list of all non-empty substrings of the string "apple" would be "apple", "appl" ,"pple" ,"app", "ppl" ,"ple","ap" ,"pp" ,"pl", "le" ,"a","p" ,"l","e". A prefix of a string S is a substring that occurs at the beginning of S.
Input format:
The fist line consists of an integer N The second fine consists of a string S of length N
Output format Print N-1 lines. The ith line denotes the answers for the prefix length i. Each line will have 3 integers denoting the count of lexicographically greater substrings, equal substrings, and smaller substrings, respectively.
Constraints 2≤ N ≤ 1e5 String S consists of lowercase English letters.
Sample Input: 5 abcba
Sample Output:
3 1 0
3 0 0
2 0 0
1 0 0
I know that the equal strings can be found by using KMP algorithm, but how to solve for lexographically smaller/larger?