@above.. It seems the above formatting has messed up.. but the point being if we calculate col by col u will get the values and it shall be easy to understand...
@sumit Hey, u don't u share ur NlogN approach and probably we can come up with something better.. On Dec 28, 3:37 pm, Lucifer <[email protected]> wrote: > For simplicity of understanding u can take a 2 dimensional array and > jolt down the values ... > > For ex - > Orig Str = abcddcabar > 10 9 8 7 6 5 4 3 2 1 > 0 r a b a c d d c b a > > 0 0 0 0 0 0 0 0 0 0 0 0 > > 1 a 0 1 > 1 1 > > 2 b 0 2 > 1 > > 3 c 0 1 > 1 > > 4 d 0 2 > 1 > > 5 d 0 1 > 3 > > 6 c 0 1 > 4 > > 7 a 0 1 1 > 1 > > 8 b 0 2 > 1 > > 9 a 0 1 3 > 2 > > 10 r 0 1 > > All the above unfilled places are actually 0s.. > Value at (6,3) gives the longest even palindrome with value 4.. > Also, (6 -4 +1 = 3) as per the start index condition.. > > On Dec 28, 2:35 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.
