이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <climits>
using namespace std;
#define F first
#define S second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x) , end(x)
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
typedef vector<pll> vpl;
typedef vector<int> vi;
ll modpow(ll b, ll e ,ll mod){
ll ans = 1;
for (; e; b = b * b % mod, e /= 2)
if (e & 1) ans = ans * b % mod;
return ans;
}
const int N = 100005;
string s;
int bigsuf = -1 , id = 2;
struct node{
int link , len , occ;
vi go;
} tree[N];
void init(){
bigsuf = 2;
id = 2;
tree[1].len = -1 , tree[1].link = 1, tree[1].go = vi(26,0) , tree[1].occ = 0;
tree[2].len = 0 , tree[2].link = 1 , tree[2].go = vi(26,0) , tree[2].occ = 0;
}
void append(int p){
int cur = bigsuf , c = s[p] - 'a';
while((p-1-tree[cur].len < 0) || s[p - 1 - tree[cur].len] != s[p])
cur = tree[cur].link;
if(!tree[cur].go[c]){
int link = tree[cur].link;
while((p-1-tree[link].len < 0) || s[p - 1 - tree[link].len] != s[p])
link = tree[link].link;
tree[cur].go[c] = ++id;
tree[id].go = vi(26,0);
tree[id].len = tree[cur].len + 2;
tree[id].link = (tree[id].len == 1 ? 2 : tree[link].go[c]);
}
bigsuf = tree[cur].go[c];
tree[bigsuf].occ ++ ;
}
int32_t main(){
int t = 1;
for(int ii = 0 ; ii < t ; ii ++){
cin >> s;
init();
for(int i = 0 ; i < sz(s) ; i++){
append(i);
}
ll ans = 0;
for(int i = id ; i > 2 ; i --){
tree[tree[i].link].occ += tree[i].occ;
ans = max(ans , (tree[i].occ * 1ll) * (tree[i].len*1ll)) ;
}
cout << ans << endl;
}
}
/* clever stuff:
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and STAY ORGANIZED
* Keep it simple stupid
* WRITE STUFF DOWN
* math -> gcd / lcm / divisors?
*/
# | 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... |