Submission #116539

#	Time	Username	Problem	Language	Result	Execution time	Memory
116539		pbt17	Palindromes (APIO14_palindrome)	C++14	100 / 100	51 ms	37524 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
 
template<int N_, int A> struct pal_tree {
 
  const static int N = N_ + 2;
 
  int n, s[N], suff[N];
  int k, len[N], occ[N], to[N][A], link[N];
 
  pal_tree() : n(0), k(0) {
    palindrome(0, 1);
    palindrome(-1, 1);
    letter(-1, 0);
  }
 
  int palindrome(int l, int suf) {
    len[k] = l;
    occ[k] = 0;
    fill_n(to[k], A, 0);
    link[k] = suf;
    return k++;
  }
 
  int letter(int val, int suf) {
    s[n] = val;
    suff[n] = suf;
    occ[suf]++;
    return n++;
  }
 
  int trim(int u) {
    while (s[n - 1 - len[u]] != s[n]) {
      u = link[u];
    }
    return u;
  }
 
  void put(int c) {
    s[n] = c; // don't delete :P
    int u = trim(suff[n - 1]);
    if (!to[u][c]) {
      int v = trim(link[u]);
      to[u][c] = palindrome(len[u] + 2, to[v][c]);
    }
    letter(c, to[u][c]);
  }
 
  int distinct() {
    return k - 2;
  }
 
  void occurrences() {
    for (int u = k - 1; u > 1; u--) {
      occ[link[u]] += occ[u];
    }
  }
 
  void clear() {
    n = 1;
  }
};
 
int main() {
  pal_tree<300000, 26> t;
  string s; cin >> s;
  for (char c : s) t.put(c - 'a');
  long long ans = 1;
  t.occurrences();
  for (int i = 2; i < t.k; i++) {
    ans = max(ans, (long long) t.occ[i] * t.len[i]);
  }
  cout << ans << endl;
}

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