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

HDU 4513

在回文子串的基础上加了限制条件, manacher算法里加个判断即可.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;

unsigned char Ma[2000005];
int Mp[2000005];

int manacher(int s[], int len) {
  int l = 0;
  Ma[l++] = '$';
  Ma[l++] = '#';
  for (int i = 0; i < len; ++i) {
    Ma[l++] = s[i];
    Ma[l++] = '#';
  }
  Ma[l] = 2;
  int mx = 0, id = 0;
  int ans = 0;
  for (int i = 0; i < l; ++i) {
    Mp[i] = mx > i ? min(Mp[2 * id - i], mx - i) : 1;
    while (Ma[i + Mp[i]] == Ma[i - Mp[i]] &&
           ((i - Mp[i]) % 2 || Ma[i - Mp[i]] <= Ma[i - Mp[i] + 2])) {
      Mp[i]++;
    }
    ans = max(ans, Mp[i] - 1);
    if (i + Mp[i] > mx) {
      mx = i + Mp[i];
      id = i;
    }
  }
  return ans;
}

int s[1000005];
int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int kase = 0, T;
  scanf("%d", &T);
  while (T--) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
      scanf("%d", &s[i]);
    }
    printf("%d\n", manacher(s, n));
  }
  return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注