Submission #307946

#	Time	Username	Problem	Language	Result	Execution time	Memory
307946		tushar_2658	Palindromes (APIO14_palindrome)	C++14	100 / 100	32 ms	36064 KiB

palindrome

#include "bits/stdc++.h"
using namespace std;

const int maxn = 600005;
using ll = long long;

int t[maxn][26], link[maxn], len[maxn];
int node, cur;
ll dp[maxn];
string s;

void init(){
  len[1] = -1;
  len[2] = 0;
  link[1] = 1;
  link[2] = 1;
  node = cur = 2;
}

void extend(int idx){
  while(s[idx - len[cur] - 1] != s[idx]){
    cur = link[cur];
  }
  int x = link[cur];
  while(s[idx - len[x] - 1] != s[idx]){
    x = link[x];
  }
  int c = s[idx] - 'a';
  if(!t[cur][c]){
    t[cur][c] = ++node;
    len[node] = len[cur] + 2;
    if(len[node] == 1){
      link[node] = 2;
    }else {
      link[node] = t[x][c];
    }
  }
  cur = t[cur][c];
  dp[cur]++;
}

int main(int argc, char const *argv[])
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> s;
  s = "#" + s;
  init();
  int n = s.size();
  for(int i = 1; i < n; ++i){
    extend(i);
  }
  ll ans = 0;
  for(int i = node; i > 2; --i){
    dp[link[i]] += dp[i];
  }
  for(int i = node; i > 2; --i){
    ans = max(ans, len[i] * 1LL * dp[i]);
  }
  cout << ans << endl;

  return 0;
}

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