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