| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 348843 | ahoraSoyPeor | Palindromes (APIO14_palindrome) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int N = 500'005;
const int MOD = 1'000'000'007;
const int LOGN = 17;
//int mul ( int A, int B ) { return int((ll(A)*ll(B))%ll(MOD)); }
//int add ( int A, int B ) { return A+B >= MOD? A+B-MOD: A+B; }
//int sub ( int A, int B ) { return add ( A, MOD-B ); }
struct palindromic_tree {
struct node{
int len, link;
map <char,int> next;
};
vector <node> pt;
int last, it;
string s;
palindromic_tree (string str = "") {
pt.reserve ( s.size()+2 );
s = '#', it = 1, last = 1; //# isn't used in string
add_node (), add_node();
pt[1].len = -1, pt[0].link = 1;
for ( char &c: str ) add_letter ( c );
}
int add_node () {
pt.push_back({});
return pt.size()-1;
}
int get_link ( int v ) {
while ( s[it-pt[v].len-2] != s[it-1] ) v = pt[v].link;
return v;
}
void add_letter ( char c ) {
s += c, ++it;
last = get_link ( last );
if ( !pt[last].next.count (c) ) {
int curr = add_node ();
pt[curr].len = pt[last].len+2;
pt[curr].link = pt[get_link(pt[last].link)].next[c];
pt[last].next[c] = curr;
}
last = pt[last].next[c];
}
node& operator[](int i) { return pt[i]; }
int size() { return pt.size(); }
};
int main () {
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
freopen ( "in.txt", "r", stdin );
#endif // LOCAL
string str;
cin >> str;
palindromic_tree root (str);
vector <pii> toSort (root.size()-2);
for ( int i = 2; i < root.size(); ++i )
toSort[i-2] = {root[i].len, i};
sort ( toSort.rbegin(), toSort.rend() );
ll maxi = 0;
for ( pii it: toSort ) {
root[root[it.ss].link].cnt += root[it.ss].cnt;
maxi = max ( maxi, root[it.ss].cnt*it.ff );
}
cout << maxi << "\n";
return 0;
}