@lucifer : little more explanation for your this algo:- *@another approach..
We can also solve the above algo in O(N^2) time and O(1) space.. Just pick an index and check whether a palindrome exits keeping the index as the center.. Complexity would be = 1 + 2 + 3 + .. + N/2 + N/2 + ... 1 = O(N^2)* On Wed, Dec 28, 2011 at 4:13 PM, Lucifer <[email protected]> wrote: > @another approach.. > > We can also solve the above algo in O(N^2) time and O(1) space.. > > Just pick an index and check whether a palindrome exits keeping the > index as the center.. > > Complexity would be = > 1 + 2 + 3 + .. + N/2 + N/2 + ... 1 = O(N^2) > > On Dec 28, 3:40 pm, Lucifer <[email protected]> wrote: > > @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. > > -- 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.
