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