ash_vs_ash's blog

Need help in practice question of EDU suffix array
By ash_vs_ash, history, 4 years ago, In English

I am continuously getting TLE on "substring search" (question 1 of step 3 ). I tried declaring global variables, tried passing reference to vectors, reduced function calls but nothing worked. According to me, my code is O(nlogn). Can someone please help me in finding why I am getting TLE. Here is the code: https://codeforces.com/edu/course/2/lesson/2/3/practice/contest/269118/submission/85793528

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Submissions in the EDU section are private, so people cant view your submissions.

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Creating (multiple) substr's per check is expensive as it involves allocation and copying of the substring.

The compare function has overloads that take start + length so you can compare the strings without creating a substr.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Finally got accepted. I didn't realize that substr would be that expensive. Thanks a lot.

    → Reply