HDU - 4513 - 吉哥系列故事――完美队形II (马拉车加判断条件)

博主链接

题目链接

题意：

在一个长度为n的数组里面找回文串，要求回文串从中间向两边一次递减

题解：

在manacher过程中添加限制语句保证题目要求即可

if(s_new[i+p[i]]!=-1111){   //如果前面位置大于当前位置，则不符合跳出
    if(s_new[i+p[i]]<=s_new[i+p[i]-2])p[i]++;
    else break;
}

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int s[100050];
int s_new[100050*2];
int p[100050*2];
int Init(int len){
    s_new[0] = -111;
    s_new[1] = -1111;
    int j = 2;
    for (int i = 0; i < len; i++){
        s_new[j++] = s[i];
        s_new[j++] = -1111;
    }
    s_new[j] = -11;  //别忘了哦
    return j;  //返回s_new的长度
}
int Manacher(int len)
{        //取得新字符串长度并完成向s_new的转换
    int maxLen = -1;   //最长回文长度
    int id;
    int mx = 0;
    for (int i = 1; i < len; i++){
        if (i < mx)
            p[i] = min(p[2 * id - i], mx - i);  //需搞清楚上面那张图含义, mx和2*id-i的含义
        else
            p[i] = 1;

        while (s_new[i - p[i]] == s_new[i + p[i]])  //不需边界判断，因为左有'$',右有'\0'
         {
            if(s_new[i+p[i]]!=-1111){   //如果前面位置大于当前位置，则不符合跳出
                if(s_new[i+p[i]]<=s_new[i+p[i]-2])p[i]++;
                else break;
            }
            p[i]++;
         }
        //我们每走一步i，都要和mx比较，我们希望mx尽可能的远，这样才能更有机会执行if (i < mx)这句代码，从而提高效率
        if (mx < i + p[i])  {
            id = i;
            mx = i + p[i];
        }
        maxLen = max(maxLen, p[i] - 1);
    }
    return maxLen;
}
int main(){
    int t;
    scanf("%d",&t);
    while (t--){
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)scanf("%d",&s[i]);
        int len=Init(n);
        printf("%d\n", Manacher(len));
    }
    return 0;
}