Submission #794637

#	Time	Username	Problem	Language	Result	Execution time	Memory
794637		cig32	Palindromes (APIO14_palindrome)	C++17	66 / 100	58 ms	52160 KiB

palindrome

#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
vector<int> pam[MAXN]; // palindromic automaton
vector<int> revfail[MAXN]; // reverse fail edges
vector<int>oddrt;
int fail[MAXN], len[MAXN], alleq[MAXN];//length=length of maximum suffix palindrome
int dp[MAXN], ans = 0;
int corr[MAXN];
void dfs(int node) {
  for(int x: revfail[node]) {
    dfs(x);
    dp[node] += dp[x];
  }
  ans = max(ans, dp[node] * len[node]); 
}
void solve(int tc) {
  string s;
  cin>>s;
  fail[0] = -1;
  len[0] = 1;
  alleq[0] = 1;
  dp[0] = 1;
  corr[0] = 0;
  oddrt.push_back(0);
  for(int i=1;i<s.size();i++){
    int nxt=corr[i-1];
    while(nxt!=-1){
      if(alleq[nxt]==1 && s[i]==s[i-1]) {
        bool done=0;
        for(int x:revfail[nxt]){
          if(s[x]==s[i] && len[x]==len[nxt]+1){
            dp[x]++;
            corr[i]=x;
            done = 1; 
            break;
          }
        }
        if(done) break;
        fail[i]=nxt;
        revfail[nxt].push_back(i);
        len[i]=len[nxt]+1;
        alleq[i]=1;
        dp[i]=1;
        corr[i]=i;
        break;
      }
      if(i-len[nxt]-1>=0 && s[i-len[nxt]-1] == s[i]) {
        bool done = 0;
        for(int x: pam[nxt]) {
          if(s[x] == s[i]) {
            dp[x]++;
            corr[i]=x;
            done = 1; 
            break;
          }
        }
        if(done) {
          break;
        }
        pam[nxt].push_back(i);
        corr[i]=i;
        dp[i]++;
        len[i] = len[nxt] + 2;
        alleq[i] = alleq[nxt] & (s[i] == s[i-1]);
        if(fail[nxt] == -1) {
          for(int x: oddrt) {
            if(s[x] == s[i]) {
              fail[i] = x;
              revfail[x].push_back(i);
              break;
            }
          }
          break;
        }
        int l = len[fail[nxt]];//original length of common prefix-suffix
        int f = fail[nxt];
        if(alleq[f] && s[i] == s[i-1]) {
          for(int x: revfail[f]) {
            if(alleq[x]) {
              fail[i] = x;
              revfail[x].push_back(i);
              break;
            }
          }
        }
        else if(s[i] == s[i-l-1]) {
          for(int x: pam[f]) {
            if(s[x] == s[i]) {
              fail[i] = x;
              revfail[x].push_back(i);
              break;
            }
          }
        }
        else {
          for(int x: oddrt) {
            if(s[x] == s[i]) {
              fail[i] = x;
              revfail[x].push_back(i);
              break;
            }
          }
        }
        break;
      }
      else nxt=fail[nxt];
    }
    if(nxt==-1) {//must be single character
      bool done=0;
      for(int x: oddrt){
        if(s[x]==s[i]){
          dp[x]++;
          corr[i]=x;
          done= 1;break;
        }
      }
      fail[i] = -1;
      if(done)continue;
      len[i] = 1;
      alleq[i] = 1;
      dp[i] = 1;
      corr[i] = i;
      oddrt.push_back(i);
    }
  }
  /*
  for(int i=0;i<s.size();i++)cout<<fail[i]<<" ";
  cout<<"\n";
  for(int i=0;i<s.size();i++)cout<<dp[i]<<" ";
  cout<<"\n";
  for(int i=0;i<s.size();i++)cout<<len[i]<<" ";
  cout<<"\n";
  for(int i=0;i<s.size();i++)cout<<alleq[i]<<" ";
  cout<<"\n";
  */
  for(int x: oddrt) dfs(x);
  cout<<ans<<"\n";
}
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
// 勿忘初衷

Compilation message (stderr)

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

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