@Lucifer : in your first approach ... i guess outer loop should start from 1 and inner loop should move n to 1..
in the given algo both outer and inner loop move from N to 1. will your algo work for this case?? string = abccba i.e when given string itself is longest even length palindrome. On Wed, Dec 28, 2011 at 3:05 PM, Lucifer <[email protected]> wrote: > Algo: > ----------- > Take the reverse of the given string and find the continuous matching > substring of even length in the orig and rev str. > > We need to take care of certain corner cases such as: > Say orig str = abadba > rev str = abdaba > > On finding the continuous substring we will get "ab" which is not a > palindrome.. > Hence to handle such cases we need need to also keep track of the > following: > 1) No. of chars matched. > 2) The start of the substring in orig str. > 3) The start of the substring in rev str when read from right to > left.. > > The above algo can be used to find all the following: > 1) Whether there is an even length palindrome > 2) Whether there is an odd length palindrome > 3) Longest even length palindrome > 4) Longest odd length palindrome > 5) Longest palindrome. > > The below code is for longest even length palindrome. > I have added a comment in the code to show where to break if we just > want to find whether it has an even palindrome. > > Time complexity is O(N^2).. > Space complexity O(N) ... > // It can as well be done in O(n^2) space but i don't see a benefit of > doing so..Hence, reduced it to O(N).. > > Lets take an array X[N+1] and initialize it to 0. > > The array will be used to record whether there is a palindrome of even/ > odd length ending at index OrigStr[i] and RevStr[j].. > > Lets say R(i, j) = length of continuous matching substring which ends > at OrigStr[i] and RevStr[j].. > > Hence, the recurrence would be, > R(i,j) = 1 + R(i-1,j-1) , if OrigStr[i] == RevStr[j] > = 0, otherwise > > If R(i,j) is even and greater than the current recorded longest even > palindrome, > then check the following before making the current max..(basically to > ensure the validity for corner cases) > > // 1 - based index for ease of understanding.. > // Basically checking for the start indices as explained above > say the substring length is K.. > If ( i - k + 1 == N - j + 1) then assign it to current max > otherwise its not a palindrome.. > > > Code: ( written based on 1-based indexing) > ---------- > char OrigStr[N]; > > for (int i =0; i < N+1 ; ++i) > X[i] = 0; > > int pStrt = 1; // to mimic the orig str > int pRev = N; // to mimic the rev str > > int currMax = 0; > > while ( pRev > 0) > { > for ( pStrt = N; pStrt >=1 ; --i) > { > if ( OrigStr[pStrt] == OrigStr[pRev] ) > { > X[pStrt] = 1 + X[pStrt - 1]; > if ( (X[pStrt] % 2 == 0) && > (currMax < X[pStrt]) && > (pStrt - X[pStrt] + 1 == pRev) > { > currMax = X[pStrt]; > // In case u r looking for any even length palindrome > // then break out from the entire loop.. > // Also, if u want to find the exact characters u can do so > by storing > // pStrt in a variable.. Using the currMax and pStrt you > can get the > // exact palindrome.. > } > } > else > X[pStrt] = 0; > } > pRev -- ; > } > > > On Dec 28, 10:57 am, sumit mahamuni <[email protected]> > wrote: > > Here I can think of O( n * log n ). can anyone think of better solution?? > > > > On Tue, Dec 27, 2011 at 11:06 PM, atul007 <[email protected]> > wrote: > > > Given a string of length N, find whether there exits an even length > > > palindrome substring. > > > what would be efficient way of solving this problem.? > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to [email protected]. > > > To unsubscribe from this group, send email to > > > [email protected]. > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > > > -- > > Thanks and Regards, > > Sumit Mahamuni. > > > > -- Slow code that scales better can be faster than fast code that doesn't > > scale! > > -- Tough times never lasts, but tough people do. > > -- I love deadlines. I like the whooshing sound they make as they fly > by. - > > D. Adams > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
