题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4513

题解：就是在Manacher判断回文串的过程中添加一条条件

Ma[i + dp[i] - 2] >= Ma[i + dp[i]]即可。

#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int M = 1e5 + 10;int s[M] , dp[M << 1] , Ma[M << 1];void Manacher(int len) {    int l = 0;    Ma[l++] = -1;    Ma[l++] = 0;    for(int i = 0 ; i < len ; i++) {        Ma[l++] = s[i];        Ma[l++] = 0;    }    Ma[l] = 0;    int mx = 0 , id = 0;    for(int i = 0 ; i < l ; i++) {        dp[i] = mx > i ? min(dp[2 * id - i] , mx - i) : 1;        while(Ma[i - dp[i]] == Ma[i + dp[i]] && Ma[i + dp[i] - 2] >= Ma[i + dp[i]]) dp[i]++;        if(dp[i] + i > mx) {            mx = dp[i] + i;            id = i;        }    }}int main() {    int t , n;    scanf("%d" , &t);    while(t--) {        scanf("%d" , &n);        for(int i = 0 ; i < n ; i++) {            scanf("%d" , &s[i]);        }        Manacher(n);        int ans = 1;        for(int i = 0 ; i < 2 * n + 2 ; i++) {            ans = max(ans , dp[i] - 1);        }        printf("%d\n" , ans);    }    return 0;}

hdu 4513（Manacher）