@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.
