Hello! I am trying to solve prefix border using suffix arrays. I have tried debugging for a long time but I cannot find why it gives WA (ignore the TLE for now). Here is the link to my solution: https://www.codechef.com/viewsolution/17597677.
I used the suffix array to get the locations of all suffixes that can make a border string with some prefix of string S. Then I make those suffixes into intervals that are sorted and processed while also handling the queries. A BIT is used to keep track of the suffixes so the kth can be found quickly. The complexity should be O(n log^2 n + (n + q) log n).
Any help would be appreciated! I’m not sure if the logic is wrong or is there a case I’m not considering.