Algo:
-----------
Take the reverse of the given string and find the continuous matching
substring of even length in the orig and rev str.
We need to take care of certain corner cases such as:
Say orig str = abadba
rev str = abdaba
On finding the continuous substring we will get "ab" which is not a
palindrome..
Hence to handle such cases we need need to also keep track of the
following:
1) No. of chars matched.
2) The start of the substring in orig str.
3) The start of the substring in rev str when read from right to
left..
The above algo can be used to find all the following:
1) Whether there is an even length palindrome
2) Whether there is an odd length palindrome
3) Longest even length palindrome
4) Longest odd length palindrome
5) Longest palindrome.
The below code is for longest even length palindrome.
I have added a comment in the code to show where to break if we just
want to find whether it has an even palindrome.
Time complexity is O(N^2)..
Space complexity O(N) ...
// It can as well be done in O(n^2) space but i don't see a benefit of
doing so..Hence, reduced it to O(N)..
Lets take an array X[N+1] and initialize it to 0.
The array will be used to record whether there is a palindrome of even/
odd length ending at index OrigStr[i] and RevStr[j]..
Lets say R(i, j) = length of continuous matching substring which ends
at OrigStr[i] and RevStr[j]..
Hence, the recurrence would be,
R(i,j) = 1 + R(i-1,j-1) , if OrigStr[i] == RevStr[j]
= 0, otherwise
If R(i,j) is even and greater than the current recorded longest even
palindrome,
then check the following before making the current max..(basically to
ensure the validity for corner cases)
// 1 - based index for ease of understanding..
// Basically checking for the start indices as explained above
say the substring length is K..
If ( i - k + 1 == N - j + 1) then assign it to current max
otherwise its not a palindrome..
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 - X[pStrt] + 1 == pRev)
{
currMax = X[pStrt];
// In case u r looking for any even length palindrome
// then break out from the entire loop..
// Also, if u want to find the exact characters u can do so
by storing
// pStrt in a variable.. Using the currMax and pStrt you
can get the
// exact palindrome..
}
}
else
X[pStrt] = 0;
}
pRev -- ;
}
On Dec 28, 10:57 am, sumit mahamuni <[email protected]>
wrote:
> Here I can think of O( n * log n ). can anyone think of better solution??
>
> On Tue, Dec 27, 2011 at 11:06 PM, atul007 <[email protected]> wrote:
> > Given a string of length N, find whether there exits an even length
> > palindrome substring.
> > what would be efficient way of solving this problem.?
>
> > --
> > 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.
>
> --
> Thanks and Regards,
> Sumit Mahamuni.
>
> -- Slow code that scales better can be faster than fast code that doesn't
> scale!
> -- Tough times never lasts, but tough people do.
> -- I love deadlines. I like the whooshing sound they make as they fly by. -
> D. Adams
--
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.
