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


  • 0
    1

    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;
    }


Log in to reply
 

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