@atul
The loop runs are correct..
Yes, it works fine for "abccba" giving out 6 as the max length of even
palindrome which is nothing but the entire string..
On Dec 29, 4:16 pm, atul anand <atul.87fri...@gmail.com> wrote:
> @Lucifer : in your first approach ...
>
> i guess outer loop should start from 1 and inner loop should move n to 1..
>
> in the given algo both outer and inner loop move from N to 1.
>
> will your algo work for this case??
>
> string = abccba
> i.e when given string itself is longest even length palindrome.
>
>
>
>
>
>
>
> On Wed, Dec 28, 2011 at 3:05 PM, Lucifer <sourabhd2...@gmail.com> 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 <sumit143smail...@gmail.com>
> > 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 <atul.87fri...@gmail.com>
> > 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 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.
>
> > > --
> > > 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 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.
