Safrout's blog

SPOJ-12713. Strings STRSOCU
By Safrout, 10 years ago, In English

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?

  • Vote: I like it
  • +4
  • Vote: I do not like it

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

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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is the latest thing I did

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

http://ideone.com/9OzGGX

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

O(n) solution with suffix automaton: 2bc3OA

→ Reply