eGoMask's blog

By eGoMask, history, 3 years ago, In English

why my this code 118446438 get Time limit exceeded and this code 118446206 get accepted in problem 1535C - Нестабильная строка

any hint

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

for(int i=0 ; i<strlen(s) ; i++)

strlen(s) has $$$O(n)$$$ complexity so this whole loop has $$$O(n^2)$$$ complexity.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

strlen() is O(n)

the way strlen works is that it will scan and count, until it finds a null character: every time you call strlen, it scans again and again from the beginning, so it's inefficient, while s.size() is constant