Submission #96693

#	Time	Username	Problem	Language	Result	Execution time	Memory
96693		fjchf02	Palindromes (APIO14_palindrome)	C++98	73 / 100	1066 ms	29432 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

const int N = 300010;

int n;
char s[N];
int a[N], gr[N], new_gr[N], ptr_gr[N], st[N], lcp[20][N];
int res[2 * N];

bool cmp(int i, int j) {
  return s[i] < s[j];
}

void calc() {
  for (int i = 0; i < n; i++) {
    a[i] = i;
  }
  sort(a, a + n, cmp);
  gr[a[0]] = 0;
  for (int i = 1; i < n; i++) {
    gr[a[i]] = gr[a[i - 1]] + (s[a[i - 1]] != s[a[i]]);
  }
  int cnt = gr[a[n - 1]] + 1;
  int step = 1;
  while (cnt < n) {
    int ptr = 0;
    for (int i = n - step; i < n; i++) {
      st[ptr++] = i;
    }
    for (int i = 0; i < n; i++) {
      if (a[i] >= step) {
        st[ptr++] = a[i] - step;
      }
    }
    for (int i = n - 1; i >= 0; i--) {
      ptr_gr[gr[a[i]]] = i;
    }
    for (int i = 0; i < n; i++) {
      int x = st[i];
      a[ptr_gr[gr[x]]++] = x;
    }
    new_gr[a[0]] = 0;
    for (int i = 1; i < n; i++) {
      if (gr[a[i]] != gr[a[i - 1]]) {
        new_gr[a[i]] = new_gr[a[i - 1]] + 1;
      } else {
        int pre = (a[i - 1] + step < n ? gr[a[i - 1] + step] : -1);
        int cur = (a[i] + step < n ? gr[a[i] + step] : -1);
        new_gr[a[i]] = new_gr[a[i - 1]] + (pre != cur);
      }
    }
    copy(new_gr, new_gr + n, gr);
    cnt = gr[a[n - 1]] + 1;
    step <<= 1;
  }
  int k = 0;
  for (int i = 0; i < n; i++) {
    if (gr[i] == n - 1) {
      k = 0;  
    } else {
      k = max(0, k - 1);
      int j = a[gr[i] + 1];
      while (i + k < n && j + k < n && s[i + k] == s[j + k]) {
        k++;
      }
      lcp[0][gr[i]] = k;
    }
  }
  for (int k = 0; k < 19; k++) {
    int len = 1 << k;
    for (int i = 0; i + 2 * len - 1 < n - 1; i++) {
      lcp[k + 1][i] = min(lcp[k][i], lcp[k][i + len]);
    }
  }
}

int solve(int x, int len) {
  x = gr[x];
  int l = x, r = x - 1;
  {
    for (int i = 19; i >= 0; i--) {
      int nx = l - (1 << i);
      if (nx >= 0 && lcp[i][nx] >= len) {
        l = nx;
      }
    }
  }
  {
    for (int i = 19; i >= 0; i--) {
      int nx = r + (1 << i);
      if (nx < n - 1 && lcp[i][r + 1] >= len) {
        r = nx;
      }
    }
  }
  return r - l + 2;
}

int main() {
  scanf("%s", s);
  n = strlen(s);
  calc();
  int cnt[26];
  fill(cnt, cnt + 26, 0);
  for (int i = 0; i < n; i++) {
    cnt[int(s[i] - 'a')]++;
  }
  long long ans = *max_element(cnt, cnt + 26);
  int l = -1, r = -1;
  for (int z = 0; z < 2 * n - 1; z++) {
    int i = (z + 1) >> 1;
    int j = z >> 1;
    int& p = res[z];
    p = (i >= r ? 0 : min(r - i, res[2 * (l + r) - z]));
    int pre = res[2 * (l + r) - z];
    while (i - p - 1 >= 0 && j + p + 1 < n && s[i - p - 1] == s[j + p + 1]) {
      p++;
      if (p >= pre) {
        int len = 2 * p + (z % 2 == 0);
        int last = i - p;
        ans = max(ans, (long long) len * solve(last, len));
      }
    }
    if (j + p > r) {
      l = i - p;
      r = j + p;
    }
  }
  printf("%lld\n", ans);
  return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s);
   ~~~~~^~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 0 / 27