Can anyone help me solve this problem?

Revision en3, by DhruvBohara, 2023-10-03 22:23:13

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?


  Rev. Lang. By When Δ Comment
en3 English DhruvBohara 2023-10-03 22:23:13 2 Tiny change: ' Output:\n3 1 0\n\' -> ' Output:\n\n3 1 0\n\'
en2 English DhruvBohara 2023-10-03 22:22:50 6 Tiny change: ':\n3 1 0\n3 0 0\n2 0 0\n1 0 0\n\' -> ':\n3 1 0\n\n3 0 0\n\n2 0 0\n\n1 0 0\n\'
en1 English DhruvBohara 2023-10-03 22:22:09 1421 Initial revision (published)