目录

• 问题
• 分析
• 代码

问题

hdu 3068 最长回文 - https://acm.hdu.edu.cn/showproblem.php?pid=3068

分析

• 暴力搜索（tle）
• 马拉车O(n)

代码

• 暴力搜索

#include<bits/stdc++.h>
using namespace std;
const int MXN = 1e5+10;
char s[MXN];
int expand(int l, int r){ // 扩展
    while(s[l] && s[r] && s[l] == s[r]) --l, ++r;
    return r - l - 1;
}
int main(){
    int t, l, r, ans;
    scanf("%d", &t);
    while(t--){
        scanf("%s", s+1), s[0] = '\0';
        l = 1, r = 1, ans = 0;
        while(s[l] && s[r]) // 两种扩展方式的初始条件：l == r 或者 r == l+1
            ans = max(ans, expand(l, r)), l == r ? ++r : ++l;
        printf("%d\n", ans);
    }
    return 0;
}

• Manacher(马拉车)

/* hdu 3068 最长回文 */
#include<bits/stdc++.h>
using namespace std;
const int MXN = 1.1e5+10;
char s[MXN<<1];
int p, R, len[MXN<<1];
int manacher(int n){
    int res = 0, l, r;
    for(int i = 1; i <= n; ++i){
        if(i >= R) l = i, r = i;
        else r = min(R, i + len[(p<<1)-i]), l = (i << 1) - r;
        while(s[l-1] && s[r+1] && s[l-1] == s[r+1]) ++r, --l;
        if(r >= R) R = r, p = i;
        len[i] = (r - l + 1) >> 1;
        res = max(res, len[i]);
    }
    return res;
}
int main(){
    int n;
    while(scanf("%s", s+MXN) == 1){
        s[0] = '\0', n = strlen(s+MXN)+1;
        for(int i = 1; i <= n; ++i) s[2*i-1] = '#', s[i<<1] = s[i+MXN-1];
        --n, p = 0, R = 0, len[0] = 0;
        printf("%d\n", manacher(n<<1|1));
    }
    return 0;
}