 problem: finding length of longest palindrome in a binary formatted number n (32 bit) .
Time limit:0.3sec

my solution:

char str;int p;

void bin(unsigned n)
{

`````` p=31;
unsigned int i;
for ( i = 1 << 31; i > 0; i = i / 2)
str[p--]= (n & i)? '1': '0';
``````

}

int longestPalSubstr()//gfg
{
int maxLength = 1;

``````int start = 0;
int len = strlen(str);

int low, high;

for (int i = 1; i < len; ++i)
{

low = i - 1;
high = i;
while (low >= 0 && high < len && str[low] == str[high])
{
if (high - low + 1 > maxLength)
{
start = low;
maxLength = high - low + 1;
}
--low;
++high;
}

low = i - 1;
high = i + 1;
while (low >= 0 && high < len && str[low] == str[high])
{
if (high - low + 1 > maxLength)
{
start = low;
maxLength = high - low + 1;
}
--low;
++high;
}
}

return maxLength;
``````

}

int main()
{

``````int t;
unsigned int n;
cin>>t;
while(t--)
{
for(int i=31;i>=0;i--)
str[i]='0';
cin>>n;
bin(n);

if(n<=32768)
{
for(int i=31;i>=0;i--)
if(str[i]=='1')
{printf("%d\n",32-i-1);
break;}
}
else
printf("%d\n",longestPalSubstr());
}
``````

}

but i have seen many solution adopting another approach may be faster, one solution of them is-

http://www.codechef.com/viewsolution/2691133

http://www.codechef.com/viewsolution/2690896

please give me hint to get that algorithm, i am new here?

1 Like

Manacher’s algorithm my friend,not Manchester’s!! too much football is bad for coders…

manchester’s algorithm O(n)

you might like to see this link to get hints:- http://tristan-interview.blogspot.in/2011/11/longest-palindrome-substring-manachers.html and http://www.akalin.cx/longest-palindrome-linear-time