Hello Coders, Suppose I have string s and I'm creating new string s1 by s1=s[j--]+s1 where j is initially (j=s.length()-1). Is this operation in C++ is time costly.
Because I was solving D2. Prefix-Suffix Palindrome (Hard version) problem.In this problem we are given string s,and we need to find string t,which satisfy given condition.
1)The length of t does not exceed the length of s.
2)t is a palindrome.
3)There exists two strings a and b (possibly empty), such that t=a+b ( "+" represents concatenation), and a is prefix of s while b is suffix of s.
I tried to solve it in following way,
1)string s1=s2="" and i=0,j=s.length()-1, now till s[i]==s[j],I added elements to s1 and s2; ie. s1+=s[i++],s2=s[j--]+s2;
2)after first step whatever string remains unused,I found longest prefix and suffix palindrome using manachers alg,and choosen max of them.
Now Main point is that when I submitted it was giving TLE on testcase 13. then I just tried to change s2=s[j--]+s2 by just only finding s1 and s2 will be obviously reverse of s1. And my code gets Accepted.
So my question is how can s2=s[j--]+s2 can be reason for TLE?
Both sols only differ in way I calculated s2.
UP1: I don't know what's wrong with some people, I have seen many comments in announcement or in tutorial section that's are either funny or sarcastic or memes ,and they gets many upvotes,I'm not saying that should not be upvoted,in fact If I like,I also upvotes them.But when some one ask for doubt most of the time it gets downvoted. IDK why?
I think many people started taking it in wrong way, they think that If they didn't like post or comment then it should be downvoted.But what is meaning of contribution? If someone if contributing to community then he should get +ve contribution and If he is spreading negativity,he should be downvoted.
But when someone ask doubt then surely he is not harming community, also he is not contributing to community either because he asked doubt for himself and it may not be useful to all people.So when someone ask doubt,two things possible either his doubts may not be useful to someone or someone having similar doubt can solve it by reading comments by others. Then how it is harming community that many are downvoting. If they thinks it is not useful they can just ignore it,what's reason for downvote.
I just tried to said what I felt after seeing downvotes on my this blog and others blogs asking for doubts,May be I will be downvoted for saying this.
Concatenation of two strings: O(|s| + |t|)
Update: You can call reserve() on the destination string(s) to avoid TLE.
s1+=s[i++] also have same complexity ? if it is,then it should be TLE or it is done differently than concatenation?
In general, yes, it also have same complexity.
Update: The C++ standard gives no guarantees for constant-time complexity of appending a character into std::basic_string. You can only expect vector-like implementation of string resizing and one day get TLE on some other compiler/stl implementation. The reply to this comment about O(1) complexity is wrong.
No. $$$s \mathrel{+}= c$$$ where $$$c$$$ is a character is $$$O(1)$$$. But $$$s = s + c$$$ is linear.
http://www.cplusplus.com/reference/string/string/append/
Actually it is implementation dependent, but in general you have to copy old content + 1 more character into a new buffer. It might be amortized to O(1) though as for vector.
Auto comment: topic has been updated by rajkumar62506 (previous revision, new revision, compare).
Auto comment: topic has been updated by rajkumar62506 (previous revision, new revision, compare).