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?
↵
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?