Insomnia 2013:Please help me to get the another algorithm for the same problem ?

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

my solution:

char str[32];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