@shady... The first approach with a slight modification will solve the above mentioned problem... I have modified the previous to show the same..
The innermost 'If' statement needs to be modified to ensure that the found substring which is present in both the originalStr and reverseStr doesn't overlap based on their respective indices and length of the found substring.. // NOTE- Earlier we had to ensure that they overlap, for the palindrome problem.. The below code basically gets the max even length substring whose reverse is also part of the origStr and doesn't overlap.. I have added comments to show where to break, in case all we need to do is find whether it contains such an even substring.. 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 < pRev) // We need to check for the case where the reverse substring is placed before the orig substring as its symmetric.. { currMax = X[pStrt]; // In case u r just looking for any even length substring // then break out from the entire loop.. } } else X[pStrt] = 0; } pRev -- ; } On Dec 29, 5:20 pm, shady <sinv...@gmail.com> wrote: > oh, i didn't read all the posts, anyway i have understood lucifier's O(n^2) > time solution. > > and ya what's the solution for this question? > Given a string of length N, find whether there exits an even length > reverse substring of a substring. > > > > > > > > On Thu, Dec 29, 2011 at 2:23 PM, atul anand <atul.87fri...@gmail.com> wrote: > > > @shady : lets go with this one:- > > > given string = *abcdrdcba > > > abcd != dcba - not a palindrome > > **abcd != dcba - **not a palindrome * > > * > > *no even length palindrome found for the given string. > > > given string = ab*cddc*abr > > > even lenght palindrome found = cddc > > > if another even length palindrome found report the longest one. > > > -- > > 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. -- 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.