I recently came to know that the operator+ is overloaded in c++ to concatenate two strings but it is highly inefficient(Complexity: linear in terms of resulting string). I searched about it but could only found either the use of Ropes or operator +=. Is there any other way of joining two strings efficiently in C++ other than these 2?
I am not very proficient in C++ , but I know that in C++ , strings are basically character arrays , thus when concatenating , all the characters of the second string would have to be copied over , making it O(N)
To make it O(1) , for storing strings simply use a linked list of characters and maintain variables for the start and end node of each linked list.
When concatenating , just join the start node of second string to the end node of first string , and call it a new string
I don’t know whether there is any library that has this implemented, although it should be pretty easy to implement by hand too
I hope I was of help
your idea is good but there exists a ds called ropes which also do string concatenation very fast and there is internal library implementing that i was just refraining from studying ropes hoping that may be there is some other way to
probably you are getting T.L.E in the 4th question of oct17
actually i was trying to submit for first subtask and + resulted a TLE for even first subtask and after changing it i got AC for 1st subtask
I Think How to rmove TLE for a live contest should not be discussed here .