@atul Can u explain your approach of hashing with an example..
On Dec 29, 12:41 am, Lucifer <sourabhd2...@gmail.com> wrote: > Editing mistake in the last sentence.. > > Now as explained above there are (N-1) interimIndices for N chars > ranging from 1 to N-1... > > On Dec 29, 12:39 am, Lucifer <sourabhd2...@gmail.com> wrote: > > > > > > > > > @sumit > > > I think even a divide conquer approach would lead to O(N^2) > > > I think the timing complexity equation would be as follows: > > > T(N) = T(N/2) + k* (N/2)^2 .. here k is a constant... > > > T(N) = O(N^2).. > > > I think your approach is same as the 2nd approach that i have > > mentioned above... > > > Please, correct me if am i wrong... > > > @atul > > > Explanation for the 2nd approach... > > > Say, given string is "ABCD" > > Now, lets define something called interimIndex which is nothing but > > the > > position between 2 chars in a string.... > > > // Considering 1-based index.. > > > Following are the indices of the the chars in the given string.. > > A - 1 > > B - 2 > > C - 3 > > D - 4 > > > Now interimIndices are the gaps between each char as shown below, > > A 1 B .. > > B 2 C.. > > C 3 D > > > Hence, for n chars there are n-1 interimIndices > > > Now, given an even palindrome, it means that the left half of the > > palindrome is a mirror image of the right half of the palindrome about > > an interimIndex. > > > For ex- say the given string is dabcddcbae ... > > Now the even palindrome in the above string is abcddcba.. > > Hence, the interimIndex for which "abcd" is a mirror image of "dcba" > > is 5. > > > From now on we will refer to a palindrome through its interimIndex.. > > > Now given an interimIndex, if we want to find the longest even > > palindrome, we need to do the following: > > Say interimIndex = K, then there are K chars towards the left and N-K > > chars towards the right. > > The longest even palindrome that can be found at K will be of size > > min(K, N-K).. > > And to find the same we will check for the equality of a char on the > > left size and corresponding mirrored char on the right half... > > The check will start from the element next to interimIndex 'K' and > > proceed away from 'K'... > > > // 1-based indexing.. > > // Code to show how check for left and right half will go on around > > the interimIndex.. > > int left = K; > > int right = N-K; > > int i = 0; > > > // After the loop finishes execution the value of 2*(i+1) will give > > the size of the longest palindrome at interimIndex 'K'.. > > while (i <min(left, right)) > > { > > if (A[K - i] == A[N-K+i] ) > > ++i; > > else > > break; > > > } > > > Now as explained above there are (N-1) for N chars ranging from 1 to > > N-1... > > Hence the running cost of the while loop will depend on min(left, > > right) which is nothing but > > > 1 + 2 + 3 + ..N/2 + N/2 + ..1 = N*(N+2)/4 = O(N^2).. > > > On Dec 28, 4:10 pm, sumit mahamuni <sumit143smail...@gmail.com> wrote: > > > > @atul : my approach is little modification of merge sort algo. > > > > 1) go to middle of string and from middle goto left and right doing > > > comparisons till you find match. > > > 2) here you found some palindrome string of length n(which is even) > > > 3) now find the even length palindrome substring for left and right half > > > recursively > > > 4) compare the results of left half and right half with total string and > > > return max substring > > > > On Wed, Dec 28, 2011 at 4:14 PM, atul anand <atul.87fri...@gmail.com> > > > wrote: > > > > @Lucifier : could you please send you explanation whose formatting in > > > > messed up. > > > > attach a test file , having your explanation. > > > > > btw can you check my algo mentioned above using hastable...it is just > > > > convenient way to solve this problem. complexity is same as your algo. > > > > > On Wed, Dec 28, 2011 at 4:10 PM, Lucifer <sourabhd2...@gmail.com> 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 <sourabhd2...@gmail.com> 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 <sourabhd2...@gmail.com> 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 <sumit143smail...@gmail.com> > > > >> > > 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 > > > >> > > > <atul.87fri...@gmail.com> > > > >> wrote: > > > >> > > > > Given a string of length N, find whether there > > ... > > read more » -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.