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