题意:

  求最长回文串。。。但这个回文串要符合从中间到两头 逐个递减

解析:

  在扩散的时候加一个判断就好了

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rep(i, a, n) for(int i=a; i<n; i++)
#define lap(i, a, n) for(int i=n; i>=a; i--)
#define lep(i, a, n) for(int i=n; i>a; i--)
#define rd(a) scanf("%d", &a)
#define rlld(a) scanf("%lld", &a)
#define rc(a) scanf("%c", &a)
#define rs(a) scanf("%s", a)
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = , INF = 0x7fffffff;
int s[maxn], s_new[maxn<<];
int p[maxn<<];
int n;
int init()
{
int len = n;
s_new[] = -;
s_new[] = -; int j = ;
for(int i=; i<len; i++)
s_new[j++] = s[i], s_new[j++] = -;
// s_new[j++] = -10;
return j;
} int manacher()
{
int len = init();
int max_len = -;
int id, mx = ; for(int i=; i<len; i++)
{
if(i < mx)
p[i] = min(p[ * id - i], mx - i); //因为这一步最初是不执行的 所以是依附于下边的扩散步骤
else
p[i] = ;
while(s_new[i-p[i]] == s_new[i+p[i]])
{
if(s_new[i+p[i]] != - && s_new[i+p[i] - ] < s_new[i+p[i]]) //不符合就跳出
break;
p[i]++;
}
if(mx < i + p[i])
{
id = i;
mx = i + p[i];
}
max_len = max(max_len, p[i] - );
}
return max_len;
} int T;
int main()
{
rd(T);
while(T--)
{
rd(n);
rep(i, , n)
rd(s[i]);
printf("%d\n", manacher()); } return ;
}
05-11 18:39