#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ll mask){return __builtin_ctzll(mask);}
int logOf(ll mask){return 63 - __builtin_clzll(mask);}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T& container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
const long K = 26;
struct PalindromeTree{
struct Node{
long child[K], layer, pi;
Node(long _layer = 0){
memset(child, -1, sizeof child);
layer = _layer;
pi = -1;
}
};
vector<Node> a;
vector<int> visit_cnt;
PalindromeTree(){
a.push_back(Node(-1)); a.push_back(Node(0));
visit_cnt.resize(3e5 + 69);
a[1].pi = a[0].pi = 0;
}
void add_child(long &x, long layer){
x = a.size();
a.push_back(Node(layer));
}
void build(string s){
long id = 0;
s = "#" + s;
for(long i = 1; i<s.size(); ++i){
visit_cnt[id]++;
long digit = s[i] - 'a';
long j = id;
while(j >= 0){
if (s[i] == s[i - a[j].layer - 1]) break;
j = a[j].pi;
}
if (a[j].child[digit] != -1) {
id = a[j].child[digit];
continue;
}
add_child(a[j].child[digit], a[j].layer + 2);
long v = a[j].child[digit];
if (a[v].layer == 1) j = 1;
else if (a[v].layer == 2) j = a[0].child[digit];
else{
j = a[j].pi;
while(j >= 0){
if (j == 0 || (s[i] == s[i - a[j].layer - 1])) break;
j = a[j].pi;
}
j = a[j].child[digit];
}
a[v].pi = j;
id = v;
}
visit_cnt[id]++;
}
};
const int N = 3e5 + 69;
vector<int> graph[N];
int depth[N];
int sum[N];
void dfs(int u, int p){
for(int v: graph[u]) if (v != p){
dfs(v, u);
sum[u] += sum[v];
}
}
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
freopen("palindrome.in", "r", stdin);
freopen("palindrome.out", "w", stdout);
string s; cin >> s;
PalindromeTree palin;
palin.build(s);
for(int i = 0; i<palin.a.size(); ++i){
depth[i] = palin.a[i].layer;
sum[i] = palin.visit_cnt[i];
if (i != 0) graph[palin.a[i].pi].push_back(i);
}
dfs(0, 0);
ll ans = 0;
for(int i = 0; i<palin.a.size(); ++i) maximize(ans, 1LL *depth[i] * sum[i]);
cout << ans << "\n";
return 0;
}
Compilation message
palindrome.cpp: In member function 'void PalindromeTree::build(std::string)':
palindrome.cpp:76:26: warning: comparison of integer expressions of different signedness: 'long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(long i = 1; i<s.size(); ++i){
| ~^~~~~~~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:133:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PalindromeTree::Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for(int i = 0; i<palin.a.size(); ++i){
| ~^~~~~~~~~~~~~~~
palindrome.cpp:142:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PalindromeTree::Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for(int i = 0; i<palin.a.size(); ++i) maximize(ans, 1LL *depth[i] * sum[i]);
| ~^~~~~~~~~~~~~~~
palindrome.cpp:125:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
125 | freopen("palindrome.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:126:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
126 | freopen("palindrome.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
10840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
10844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
10844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
10844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
10840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
