2017 Platinum - Standing Out From the Herd

Problems and Contests
#1

I’m currently reading the official solution to the 2017 platinum question standing out.

I understood everything in the text part of the editoral, but i’m confused with the ‘compute_lcp’ function in the code. As i understand it(correct me if im wrong), the function computes the left longest common prefix for each suffix in the combined string(all the names concatonated with ‘$’ in between). If so, wouldn’t this function TLE and take n^2 to run(for example, if we had a string of length 10^5 of all the same character)?

#2

Well, try it and see. But it should run in O(n) time (it’s known as Kasai’s algorithm, and is described here: Suffix Array - Algorithms for Competitive Programming).

1 Like
#3

Now i see. Thank you!