LightOJ – 1258 Making Huge Palindromes

Making Huge Palindromes

通过对字符串添加最少的字母,使其变为回文串,有点意思.
用manacher求出原串中能覆盖其后缀并且最左端最前的回文子串,这样原串左端没有被回文子串覆盖的部分就是要添加的了.

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

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

int manacher(char 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] = 0;
  int mx = 0, id = 0;
  int ans = len - 1;
  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]]) {
      Mp[i]++;
    }
    if ((i - Mp[i]) / 2 < ans && i + Mp[i] == l) {
      ans = (i - Mp[i]) / 2;
    }
    if (i + Mp[i] > mx) {
      mx = i + Mp[i];
      id = i;
    }
  }
  return ans + len;
}

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

发表评论

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