For simplicity of understanding u can take a 2 dimensional array and
jolt down the values ...
For ex -
Orig Str = abcddcabar
10 9 8 7 6 5 4 3 2 1
0 r a b a c d d c b a
0 0 0 0 0 0 0 0 0 0 0 0
1 a 0 1
1 1
2 b 0 2
1
3 c 0 1
1
4 d 0 2
1
5 d 0 1
3
6 c 0 1
4
7 a 0 1 1
1
8 b 0 2
1
9 a 0 1 3
2
10 r 0 1
All the above unfilled places are actually 0s..
Value at (6,3) gives the longest even palindrome with value 4..
Also, (6 -4 +1 = 3) as per the start index condition..
On Dec 28, 2:35 pm, Lucifer <[email protected]> wrote:
> 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.
