Submission #1095814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095814		vjudge1	Palindromes (APIO14_palindrome)	C++17	100 / 100	23 ms	35160 KiB

palindrome

// Palindromic Tree

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 3e5+5;
const int A = 26;

string s;
int to[N][A], len[N], lnk[N], u, cnt, occ[N];

void init() {
  while (cnt >= 0) {
    memset(to[cnt], 0, sizeof(to[cnt]));
    occ[cnt] = 0;
    cnt--;
  }
  len[1] = -1;
  lnk[1] = lnk[2] = 1;
  u = cnt = 2;
}

void add(int i) {
  while (s[i - 1 - len[u]] != s[i]) u = lnk[u];
  int c = s[i] - 'a', v = lnk[u];
  while (s[i - 1 - len[v]] != s[i]) v = lnk[v];
  if (!to[u][c]) {
    to[u][c] = ++cnt;
    len[cnt] = len[u] + 2;
    lnk[cnt] = len[cnt] == 1? 2: to[v][c];
  }
  u = to[u][c];
  occ[u]++;
}

void solve () {
  cin >> s;
  s = " " + s;
  init();
  for (int i = 1; i < s.size(); ++i) {
    add(i);
  }
  ll ans = 0;
  for (int i = cnt; i > 2; --i) {
    occ[lnk[i]] += occ[i];
    ans = max(ans, 1ll * len[i] * occ[i]);
  }
  cout << ans << "\n";
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  solve();
  return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'void solve()':
palindrome.cpp:41:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for (int i = 1; i < s.size(); ++i) {
      |                   ~~^~~~~~~~~~

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