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?
Auto comment: topic has been updated by DhruvBohara (previous revision, new revision, compare).
Auto comment: topic has been updated by DhruvBohara (previous revision, new revision, compare).
You can use z_function to solve in O(n).
Can u please explain how???
I was able to come up with a nlogn approach-> Lets create 3 prefix sum array for greater,equal and less....now first of all we check for prefix of length 1. Store the count of numbers index are greater than s[0] in the prefix sum array of greater than...for ex in the above testcase index 2,3,4 have character greater than s[0] so just increase the gretaer[1] by 1 and reduce gretaer[5] by -1 for b...same goes for c,increase greater[1] by 1 and greater[4] by -1 because this c cnt contribute in prefix length gretaer than 3(as we have atmax 3 after it) do it for all the characters gretaer than it....do the same for less than prefix sum array...now if we observe that once a lexicographically gretaer string will always be lexicographically gretaer so there is no need to change in greater and less but the equal character may be included in lesser or greater as we increase their length....so for equal charcaters find the first index where it diff from prefix(can be done in logn by hashing)...let it be of length i...increase equal[1] by 1 and equal[i+1] by -1...now if the next element is smaller than it goes to lesser otherwise gretaer...so you increase the corresponding sum in lesser or greater array
now do pre[i]+=pre[i-1] for all the three arrays
just print gretaer[i] equal[i] lesser[i] for all the arrays for the final answer of a i
Can u provide code for better understanding????
here
Thanku!!!