@RAJ Can u explain ur dp approach... For ex- what is i and j in LP(i,j) ?
On 29 Dec, 19:14, Lucifer <[email protected]> wrote: > @Editing mistake for the comment in the innermost 'If' loop.. > > We need *not check for the case where the reverse substring is placed > before the orig substring as its symmetric.. > > On Dec 29, 7:12 pm, Lucifer <[email protected]> wrote: > > > > > > > > > @shady > > > I am re-posting the code.. Somehow the format is getting messed up... > > > 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 looking for any even length palindrome > > // then break out from the entire loop.. > > } > > } > > else > > X[pStrt]=0; > > } > > > pRev -- ; > > > } > > > On Dec 29, 7:03 pm, Lucifer <[email protected]> wrote: > > > > @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 <[email protected]> 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 <[email protected]> > > > > 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 [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.
