# (AC) 3ms C Manacher's Algorithm O(n) solution

• char* init(char*,int*);
int find_head(int,int);

char* longestPalindrome(char* s) {
int len_s=strlen(s);
int len;
char* result;
result=init(s,&len);
int* RL=malloc(sizeof(int)*len);//建構RL數據組.
memset(RL,0,sizeof(int)*len);
#if(0)
for(int i=0;i<len;i++)
{
printf("%c",result[i]);
}
printf("\n");
#endif
int pos=0,mx=0,maxlen=0,maxpos=0;//對稱點 最大右邊界 最長回文長度 最大回文長度對稱點.
for(int i=0;i<len;i++)
{
if(mx-i>0)
{
int i=(pos<<1)-i;
RL[i]=(RL[i]<mx-i)?RL[i]:mx-i;
}
else
{
RL[i]=1;
}
int left=i-RL[i],right=i+RL[i];//已i為對稱點探索左邊界及右邊界.
while(left>=0 && right<len && (result[left]==result[right]))
{
++RL[i];
left=i-RL[i],right=i+RL[i];
}
if(right>mx)
{
mx=right;
pos=i;
}
if(maxlen<RL[i])
{
maxlen=RL[i];
maxpos=i;
}
}
maxlen=maxlen-1;//特性原始字串最長回文長度等於maxlen-1
printf("%d\n",maxlen);
int h=find_head(maxpos,maxlen);

``````h=(h==0)?0:h;
s[h+maxlen]='\0';
s+=h;
return s;
``````

}

//將字串做點變化如aba→#a#b#a#
char* init(char* s,int* len)
{
int len_s=strlen(s);
len_s=(len_s<<1)+1;
char* result=malloc(len_s);
for(int i=0,j=0;i<len_s;i++)
{
result[i]=(i%2==0)?'#':s[j++];
}
*len=len_s;
return result;
}

int find_head(int pos,int len)
{
int head;
printf("pos=%d len=%d\n",pos,len);
head=pos-len;
head>>=1;
printf("head=%d",head);
return head;
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.