最长回文串算法

给定一个字符串,求它的最长回文子串的长度。

/**
 * @param s 
 * @param n 
 * @return 
 */
bool IsPalindrome(const char *s, int n){
    if(s== NULL||n<1){
        return false;
    }
    for (int i = 0; i < n/2; ++i) {
        if(s[i]!=s[n-i-1]){
            return false;
        }
    }
    return true;
}/**
 * 穷举法遍历所有长度 O(n^3)
 * @param s
 * @param n
 * @return
 */
int LongestPalindrome(const char *s, int n){
    if(s== nullptr||n<1){
        return 0;
    }
    int longest=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=n-i;j++){
            if(IsPalindrome(s+j,i)){
                longest=longest<i?i:longest;
            }
        }
    }
    return longest;
}
/**
 * 找中心点向外扩散 O(n^2)
 * @param s
 * @param n
 * @return
 */
int LongestPalindrome2(const char *s, int n){
    if(s== nullptr||n<1){
        return 0;
    }
    int longest=0;//长度
    //i是中心点下标
    for (int i = 0; i <n ; ++i) {
        //j是长度
        //奇数串
        for (int j = 0;(i-j)>=0&&(i+j)<n; ++j) {
            if(s[i-j]!=s[i+j]){
                break;
            }
            int c=j*2+1;
            longest=longest<c?c:longest;
        }
        for (int j = 0;(i-j)>=0&&(i+j+1)<n; ++j) {
            if(s[i-j]!=s[i+j+1]){
                break;
            }
            int c=j*2+2;
            longest=longest<c?c:longest;
        }
    }
    return longest;

}
/**
 * Manacher算法 O(n)
 * @param s
 * @param n
 * @return
 */
int LongestPalindrome3(const char *s, int n){
    if(s== nullptr||n<1){
        return 0;
    }
    char str[n*2+4];
    int j=0;
    str[j++]='$';
    str[j++]='#';

    for (int i = 0; i < n; ++i) {
        //使回文串长度变成偶数
        str[j++]=*(s+i);
        str[j++]='#';
    }
    str[j]='\0';
    int p[j-1];//保存以下标为中心点的最长回文串长度
    memset(p,0, sizeof(p));
    int mx=0;//回文串最右边界
    int idx=0;//回文串中心点
    int longest=0;//最长子串
    for(int i=1;i<j-1;i++){
        p[i]=mx>i?min(mx-i,p[2*idx-i]):1;//2*idx-i 与i关于idx对称,如果p[2*idx-i]比mx-i长则说明p[i]>=p[2*idx-i] 短的话 p[i]=p[2*idx-i]
        while(str[i-p[i]]==str[i+p[i]]){
            p[i]++; //继续求p[i]的最长回文串
        }
        longest=p[i]>longest?p[i]:longest;
        if(p[i]+i>mx){
            mx=p[i]+i;
            idx=i;
        }
    }
    return longest-1;
} 

Leave a Reply

Time limit is exhausted. Please reload CAPTCHA.

This site uses Akismet to reduce spam. Learn how your comment data is processed.