이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <unordered_map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define INF 1100000000
#define INFLL 1000000000000000000ll
#define ii pair<int,int>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define M1 1000000007ll
#define M2 1000000009ll
#define UQ(x) (x).resize(distance((x).begin(), unique(all(x))))
#define rep(i,a,b) for (int i = (a); i < (b); i++)
template<typename T> bool ckmax(T& a, T const& b) {return b>a?a=b,1:0;}
template<typename T> bool ckmin(T& a, T const& b) {return b<a?a=b,1:0;}
using vi = vector<int>;
struct PalTree {
static const int ASZ = 26;
struct node {
array<int,ASZ> to = array<int,ASZ>();
int len, link, oc = 0; // # occurrences of pal
int slink = 0, diff = 0;
array<int,2> seriesAns;
node(int _len, int _link) : len(_len), link(_link) {}
};
string s = "@"; vector<array<int,2>> ans = {{0,INF}};
vector<node> d = {{0,1},{-1,0}}; // dummy pals of len 0,-1
int last = 1;
int getLink(int v) {
while (s[sz(s)-d[v].len-2] != s.back()) v = d[v].link;
return v;
}
void updAns() { // serial path has O(log n) vertices
ans.pb({INF,INF});
for (int v = last; d[v].len > 0; v = d[v].slink) {
d[v].seriesAns=ans[sz(s)-1-d[d[v].slink].len-d[v].diff];
if (d[v].diff == d[d[v].link].diff)
rep(i,0,2) ckmin(d[v].seriesAns[i],
d[d[v].link].seriesAns[i]);
// start of previous oc of link[v]=start of last oc of v
rep(i,0,2) ckmin(ans.back()[i],d[v].seriesAns[i^1]+1);
}
}
void addChar(char C) {
s += C; int c = C-'a'; last = getLink(last);
if (!d[last].to[c]) {
d.emplace_back(d[last].len+2,d[getLink(d[last].link)].to[c]);
d[last].to[c] = sz(d)-1;
auto& z = d.back(); z.diff = z.len-d[z.link].len;
z.slink = z.diff == d[z.link].diff
? d[z.link].slink : z.link;
} // max suf with different dif
last = d[last].to[c]; ++d[last].oc;
updAns();
}
void numOc() { for (int i=sz(d)-1;i>=2;i--) d[d[i].link].oc += d[i].oc; }
ll solve() {
numOc();
ll ans = 0;
for (auto &x:d) {
ckmax(ans, (ll)x.len*(ll)x.oc);
}
return ans;
}
};
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
string s;
cin>>s;
PalTree p;
for (int i=0;i<sz(s);i++) {
p.addChar(s[i]);
}
cout << p.solve() << '\n';
}
// int dp[maxn][2]; // dp(i,b) = min number of palindromes split with parity b
// int main() {
// scanf("%s",t);
// int l = strlen(t);
// init();
// for (int i = 0; i < l; i++) {
// add_letter(t[i]-'a');
// if (i == 0) {
// dp[0][0] = INF;
// dp[0][1] = 1;
// } else {
// }
// }
// printf("%s\n", t);
// }
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |