Блог пользователя ash_vs_ash

Need help in practice question of EDU suffix array
Автор ash_vs_ash, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

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

    → Ответить