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

SPOJ-12713. Strings STRSOCU
Автор Safrout, 9 лет назад, По-английски

I have wrote an O(n^2) solution for this problem

http://www.spoj.com/problems/STRSOCU/

here is my code

http://ideone.com/hEO6jv

What could be a better Solution for it?

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

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

I tried to optimize it a little bit and write it in C++ but it also gives TLE http://ideone.com/fb4hv5 I do not concatenate n times but i give the Z-function a number k to start matching from the character at index k It works correctly and the Z-values are correct but the time is too much

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

This is the latest thing I did

I think I can't optimize more in an O(n^2) code

http://ideone.com/9OzGGX

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

O(n) solution with suffix automaton: 2bc3OA

→ Ответить