@atul : my approach is little modification of merge sort algo.
1) go to middle of string and from middle goto left and right doing
comparisons till you find match.
2) here you found some palindrome string of length n(which is even)
3) now find the even length palindrome substring for left and right half
recursively
4) compare the results of left half and right half with total string and
return max substring
On Wed, Dec 28, 2011 at 4:14 PM, atul anand <atul.87fri...@gmail.com> wrote:
> @Lucifier : could you please send you explanation whose formatting in
> messed up.
> attach a test file , having your explanation.
>
> btw can you check my algo mentioned above using hastable...it is just
> convenient way to solve this problem. complexity is same as your algo.
>
> On Wed, Dec 28, 2011 at 4:10 PM, Lucifer <sourabhd2...@gmail.com> wrote:
>
>> @above..
>>
>> It seems the above formatting has messed up.. but the point being if
>> we calculate col by col u will get the values and it shall be easy to
>> understand...
>>
>> @sumit
>> Hey, u don't u share ur NlogN approach and probably we can come up
>> with something better..
>>
>>
>> On Dec 28, 3:37 pm, Lucifer <sourabhd2...@gmail.com> wrote:
>> > 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 <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.
>
--
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.
