@sumit
I think even a divide conquer approach would lead to O(N^2)
I think the timing complexity equation would be as follows:
T(N) = T(N/2) + k* (N/2)^2 .. here k is a constant...
T(N) = O(N^2)..
I think your approach is same as the 2nd approach that i have
mentioned above...
Please, correct me if am i wrong...
@atul
Explanation for the 2nd approach...
Say, given string is "ABCD"
Now, lets define something called interimIndex which is nothing but
the
position between 2 chars in a string....
// Considering 1-based index..
Following are the indices of the the chars in the given string..
A - 1
B - 2
C - 3
D - 4
Now interimIndices are the gaps between each char as shown below,
A 1 B ..
B 2 C..
C 3 D
Hence, for n chars there are n-1 interimIndices
Now, given an even palindrome, it means that the left half of the
palindrome is a mirror image of the right half of the palindrome about
an interimIndex.
For ex- say the given string is dabcddcbae ...
Now the even palindrome in the above string is abcddcba..
Hence, the interimIndex for which "abcd" is a mirror image of "dcba"
is 5.
>From now on we will refer to a palindrome through its interimIndex..
Now given an interimIndex, if we want to find the longest even
palindrome, we need to do the following:
Say interimIndex = K, then there are K chars towards the left and N-K
chars towards the right.
The longest even palindrome that can be found at K will be of size
min(K, N-K)..
And to find the same we will check for the equality of a char on the
left size and corresponding mirrored char on the right half...
The check will start from the element next to interimIndex 'K' and
proceed away from 'K'...
// 1-based indexing..
// Code to show how check for left and right half will go on around
the interimIndex..
int left = K;
int right = N-K;
int i = 0;
// After the loop finishes execution the value of 2*(i+1) will give
the size of the longest palindrome at interimIndex 'K'..
while (i <min(left, right))
{
if (A[K - i] == A[N-K+i] )
++i;
else
break;
}
Now as explained above there are (N-1) for N chars ranging from 1 to
N-1...
Hence the running cost of the while loop will depend on min(left,
right) which is nothing but
1 + 2 + 3 + ..N/2 + N/2 + ..1 = N*(N+2)/4 = O(N^2)..
On Dec 28, 4:10 pm, sumit mahamuni <[email protected]> wrote:
> @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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[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.
>
> > --
> > 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.
