Submission #795256

#	Time	Username	Problem	Language	Result	Execution time	Memory
795256		cig32	Palindromic Partitions (CEOI17_palindromic)	C++17	60 / 100	451 ms	131072 KiB

palindromic

#include "bits/stdc++.h"
using namespace std;
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 << ": "; }
struct palindromic_automaton {
  vector<vector<int> >pam;
  vector<vector<int> >revfail;
  vector<int> oddrt,evenrt,fail,len,alleq,corr;
  vector<int> cnt;
  vector<int> dif,slink;
  string s;//the string itself
  // Declare other variables here
  void init(int n) {
    pam.resize(n + 5);
    revfail.resize(n + 5);
    fail.resize(n + 5);
    len.resize(n + 5);
    alleq.resize(n + 5);
    corr.resize(n + 5);
    cnt.resize(n + 5);
    dif.resize(n + 5);
    slink.resize(n + 5);
    // Initialize other arrays here
  }
  void append(char c) {
    int i = s.size();
    s += c;
    if(i == 0) {
      fail[0] = -1;
      len[0] = 1;
      alleq[0] = 1;
      corr[0] = 0;
      cnt[0] = 1;
      dif[0] = 0;
      slink[0] = -1;
      oddrt.push_back(0);
      return;
    }
    int nxt=corr[i-1];
    while(nxt!=-1){
      if(alleq[nxt] && s[i]==s[i-1]) {
        bool done=0;
        for(int x:revfail[nxt]){
          if(s[x]==s[i] && len[x]==len[nxt]+1){
            corr[i]=x;
            cnt[x]++;
            done = 1; 
            break;
          }
        }
        if(done) break;
        fail[i]=nxt;
        revfail[nxt].push_back(i);
        len[i]=len[nxt]+1;
        alleq[i]=1;
        corr[i]=i;
        cnt[i]=1;
        break;
      }
      if(i-len[nxt]-1>=0 && s[i]==s[i-len[nxt]-1]) {
        bool done=0;
        for(int x:pam[nxt]){
          if(s[x]==s[i]){
            done=1;
            corr[i]=x;
            cnt[x]++;
            break;
          }
        }
        if(done)break;
        pam[nxt].push_back(i);
        corr[i]=i;
        cnt[i]=1;
        len[i]=len[nxt]+2;
        alleq[i]=alleq[nxt]&(s[i]==s[i-1]);
        int again=nxt;
        fail[i]=-1;
        while(fail[again]!=-1){
          again=fail[again];
          if(i-len[again]-1>=0 && s[i-len[again]-1]==s[i]){
            for(int x:pam[again]){
              if(s[x]==s[i]&&len[x]==len[again]+2){
                fail[i]=x;
                revfail[x].push_back(i);
                break;
              }
            }
            break;
          }
          if(alleq[again] && s[i]==s[i-1]){
            for(int x:revfail[again]){
              if(s[x]==s[i]&&len[x]==len[again]+1){
                fail[i]=x;
                revfail[x].push_back(i);
                break;
              }
            }
            break;
          }
        }
        if(fail[i]==-1){
          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){//single character
      bool done=0;
      for(int x: oddrt){
        if(s[x]==s[i]){
          corr[i]=x;
          cnt[x]++;
          done= 1;break;
        }
      }
      if(!done) {
        fail[i] = -1;
        len[i] = 1;
        alleq[i] = 1;
        corr[i] = i;
        cnt[i] = 1;
        oddrt.push_back(i);
      }
    }
    if(len[i] == 2) evenrt.push_back(i);
    dif[i] = len[i] - (fail[i] == -1 ? 0 : len[fail[i]]);
    if(fail[i] == -1 || dif[i] != dif[fail[i]]) slink[i] = fail[i];
    else slink[i] = slink[fail[i]];
  }
  public:
};
void solve(int tc) {
  string s;
  cin >> s;
  int n = s.size();
  int l = 0, r = n - 1;
  int dp[n], g[n];
  for(int i=0; i<n; i++) dp[i] = g[i] = 0;
  palindromic_automaton t;
  t.init(n);
  for(int i=0; i<n; i++) {
    if(i % 2 == 0) t.append(s[l++]);
    else t.append(s[r--]);
    dp[i]=-1e9;
    for(int x=t.corr[i];x>0;x=t.slink[x]) {
      if(i-(t.slink[x]==-1?0:t.len[t.slink[x]])-t.dif[x] >= 0) {
        g[x]=dp[i-(t.slink[x]==-1?0:t.len[t.slink[x]])-t.dif[x]];
      }
      else if(i-(t.slink[x]==-1?0:t.len[t.slink[x]])-t.dif[x] == -1) {
        g[x]=0;
      }
      if(t.dif[x]==t.dif[t.fail[x]]) g[x]=max(g[x],g[t.fail[x]]);
      if(i%2 == 1) dp[i] = max(dp[i], g[x] + 1);
    }
  }
  int ans = dp[n-1] * 2;
  for(int i=0; i+1<n; i++) ans = max(ans, dp[i] * 2 + 1);
  ans = max(ans, 1);
  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);
}
// 勿忘初衷

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 0 / 40