제출 #747754

#제출 시각아이디문제언어결과실행 시간메모리
747754Prieved1회문 (APIO14_palindrome)C++17
0 / 100
63 ms73680 KiB
#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]=0;
    }
    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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...