吉哥系列故事——完美队形II HDU

题目链接

题意：求一个数组的回文串且满足条件为三角形，从小到大然后到小。

思路：在马拉车算法寻找右边len数组时添加判断条件即可。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX_N = 1e6+9;
int str[MAX_N];
int s[MAX_N<<1];
int len[MAX_N<<1];
int init(int N)
{
    s[0] = 0;
    for(int i=1;i<=2*N;i+=2)
    {
        s[i] = 1;
        s[i+1] = str[i/2];
    }
    s[2*N+1] = 1;
    s[2*N+2] = -1;
    return 2*N+1;
}
int manacher(int ll)
{
    int mx = 0 , po = 0;
    int ans = 0;
    for(int i=1;i<=ll;i++)
    {
        if(mx > i) len[i] = min(mx-i,len[2*po-i]);
        else len[i] = 1;
        while(s[i-len[i]] == s[i+len[i]])
        {
            if(s[i+len[i]]!=1&&s[i+len[i]-2]<s[i+len[i]])
            {
                break;
            }
            len[i] ++ ;
        }
        if(len[i]+i > mx )
        {
            mx = len[i]+i;
            po = i;
        }
        ans = max(ans , len[i]-1);
    }
    return ans;
}
int main()
{
    int T,N,M=1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&N);
        for(int i=0;i<N;i++) 
            scanf("%d",&str[i]);
        int ll=init(N);
        int ans=manacher(ll);
        printf("%d
",ans);
    }
}