欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU 3068 ( 最长回文 )

程序员文章站 2024-02-24 17:59:58
...

Problem : 3068 ( 最长回文 )     Judge Status : Accepted
RunId : 6255711    Language : C++    Author : ssun
Code Render Status : Rendered By HDOJ C++ Code Render Version 0.01 Beta
#include "stdio.h"
#include "string.h"
#define N 2200050

char str[N],nstr[2*N];
int rad[2*N];
int len,nlen;

int manacher(){
    int id, i, ans = 1;
    int mx = 0;
//    printf("%d",strlen(nstr));
    for(i=1; i<nlen; i++){//$#1#2#3#3#2#1#不要用strlen(nstr)代替nlen
        if(mx > i)
            rad[i] = mx - i < rad[2*id-i] ? mx - i : rad[2*id-i];
        else
            rad[i] = 1;
        for(;nstr[i+rad[i]] == nstr[i-rad[i]];rad[i]++)
            ;

        if(rad[i] + i > mx){
            mx = rad[i] + i;
            id = i;
        }

        ans = rad[i] > ans ? rad[i] : ans;
    }
    return ans-1;
}

int main(){
    while(scanf("%s",str)!=EOF){
        int i=0;
//        memset(rad,0,sizeof(rad));
        nstr[0] = '$';
        nstr[1] = '#';
        len = strlen(str);
        for(i=0; i<len; i++){
            nstr[2*i+3] = '#';
            nstr[2*i+2] = str[i];            
        }
        nstr[2*i+2] = 0;
        nlen = 2 * len + 2;
        printf("%d\n",manacher());
    }
    return 0;
}

参考http://bbs.dlut.edu.cn/bbstcon.php?board=Competition&gid=23474Manacher算法的解释

其实值得一提的是这个程序的manacher()函数里面的for循环不要用strlen()函数,不然的话会超时,不用strlen函数而用nlen = 2 * len + 2的话250ms可以过