Submission #747755

#	Time	Username	Problem	Language	Result	Execution time	Memory
747755		Prieved1	Palindromes (APIO14_palindrome)	C++17	0 / 100	790 ms	73404 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
const int N=300000+100;
int sz[N], snext[N];
int child[N][27], cnt[N];
vector<int> g[N];
long long dp[N];
void dfs(int at) {
  dp[at]=cnt[at];
  for(int to:g[at]) {
    if(to==at)continue;
    dfs(to);
    dp[at]+=dp[to];
  }
}
int main () {
  cin.tie(0)->sync_with_stdio(0);
  string s;
  cin >> s;
  int n=s.size();
  int pt=0;
  sz[0]=0;
  sz[1]=-1;
  snext[0]=1;
  snext[1]=1;
  int nodecnt=2;
  for(int i = 0;i<n;i++) {
    int cur=pt;
    while(cur!=1 and ((i-sz[cur]-1)<0 or s[i-sz[cur]-1]!=s[i]))cur=snext[cur];
    int curnode=nodecnt++;
    child[cur][s[i]-'a']=curnode;
    pt=curnode;
    sz[curnode]=sz[cur]+2;
    cnt[pt]++;
    if(cur==1) {
      snext[curnode]=child[0][s[i]-'a'];
    }
    else {
      cur=snext[cur];
      while(cur!=1 and ((i-sz[cur]-1)<0 or s[i-sz[cur]-1]!=s[i]))cur=snext[cur];
      snext[curnode]=child[cur][s[i]-'a'];
    }
    g[snext[curnode]].push_back(curnode);
  }
  dfs(0);
  long long res=0;
  for(int i = 2;i<=n+2;i++) {
    res=max(res, sz[i]*dp[i]);
  }
  cout << res << "\n";
  return 0;
}

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