#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
#define out(x) "{" << (#x) << ": " << x << "} "
const ll MAX_N = 1e6 + 10;
struct PalindromicTree {
map<char, ll> mp[MAX_N];
ll link[MAX_N], len[MAX_N], times[MAX_N];
ll cnt, last;
void init() {
for(ll i = 0; i < cnt; i ++) {
mp[i].clear();
}
cnt = 2;
last = 1;
len[0] = -1; link[0] = 0;
len[1] = 0; link[1] = 0;
}
void build(const string &text) {
for(ll i = 0; i < text.size(); i ++) {
while(true) {
if(text[i - len[last] - 1] == text[i]) {
ll curr;
if(mp[last].find(text[i]) == mp[last].end()) {
curr = cnt ++;
mp[last][text[i]] = curr;
} else {
curr = mp[last][text[i]];
}
len[curr] = len[last] + 2;
while(true) {
if(text[i - len[last] - 1] == text[i] && mp[last].find(text[i]) != mp[last].end() && mp[last][text[i]] != curr) {
link[curr] = mp[last][text[i]];
break;
} else if(last == 0) {
link[curr] = 1;
break;
} else {
last = link[last];
}
}
last = curr;
break;
} else {
last = link[last];
}
}
times[last] ++;
}
}
void dfs(int x, string out) {
for(auto it : mp[x]) {
if(x == 0) {
dfs(it.second, string(1, it.first));
} else {
dfs(it.second, string(1, it.first) + out + string(1, it.first));
}
}
}
ll getAns() {
ll ret = -1;
for(ll i = cnt - 1; i >= 0; i --) {
times[link[i]] += times[i];
chkmax(ret, (ll)times[i] * (ll)len[i]);
}
return ret;
}
};
PalindromicTree pt;
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
string in;
cin >> in;
pt.init();
pt.build(in);
cout << pt.getAns() << endl;
return 0;
pt.dfs(0, "");
pt.dfs(1, "");
return 0;
}
Compilation message
palindrome.cpp: In member function 'void PalindromicTree::build(const string&)':
palindrome.cpp:29:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(ll i = 0; i < text.size(); i ++) {
| ~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
47340 KB |
Output is correct |
2 |
Correct |
30 ms |
47340 KB |
Output is correct |
3 |
Correct |
30 ms |
47340 KB |
Output is correct |
4 |
Correct |
30 ms |
47340 KB |
Output is correct |
5 |
Correct |
30 ms |
47340 KB |
Output is correct |
6 |
Correct |
31 ms |
47340 KB |
Output is correct |
7 |
Correct |
31 ms |
47340 KB |
Output is correct |
8 |
Correct |
30 ms |
47340 KB |
Output is correct |
9 |
Correct |
35 ms |
47340 KB |
Output is correct |
10 |
Correct |
30 ms |
47340 KB |
Output is correct |
11 |
Correct |
30 ms |
47340 KB |
Output is correct |
12 |
Correct |
30 ms |
47340 KB |
Output is correct |
13 |
Correct |
30 ms |
47340 KB |
Output is correct |
14 |
Correct |
30 ms |
47340 KB |
Output is correct |
15 |
Correct |
30 ms |
47340 KB |
Output is correct |
16 |
Correct |
30 ms |
47340 KB |
Output is correct |
17 |
Correct |
30 ms |
47340 KB |
Output is correct |
18 |
Correct |
30 ms |
47340 KB |
Output is correct |
19 |
Correct |
32 ms |
47340 KB |
Output is correct |
20 |
Correct |
30 ms |
47340 KB |
Output is correct |
21 |
Correct |
32 ms |
47340 KB |
Output is correct |
22 |
Correct |
31 ms |
47340 KB |
Output is correct |
23 |
Correct |
31 ms |
47340 KB |
Output is correct |
24 |
Correct |
31 ms |
47340 KB |
Output is correct |
25 |
Correct |
35 ms |
47340 KB |
Output is correct |
26 |
Correct |
32 ms |
47340 KB |
Output is correct |
27 |
Correct |
35 ms |
47340 KB |
Output is correct |
28 |
Correct |
32 ms |
47340 KB |
Output is correct |
29 |
Correct |
30 ms |
47340 KB |
Output is correct |
30 |
Correct |
30 ms |
47340 KB |
Output is correct |
31 |
Correct |
30 ms |
47340 KB |
Output is correct |
32 |
Correct |
30 ms |
47340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
47468 KB |
Output is correct |
2 |
Correct |
30 ms |
47468 KB |
Output is correct |
3 |
Correct |
30 ms |
47468 KB |
Output is correct |
4 |
Correct |
30 ms |
47468 KB |
Output is correct |
5 |
Correct |
30 ms |
47468 KB |
Output is correct |
6 |
Correct |
31 ms |
47468 KB |
Output is correct |
7 |
Correct |
34 ms |
47468 KB |
Output is correct |
8 |
Correct |
30 ms |
47468 KB |
Output is correct |
9 |
Correct |
30 ms |
47340 KB |
Output is correct |
10 |
Correct |
30 ms |
47340 KB |
Output is correct |
11 |
Correct |
30 ms |
47340 KB |
Output is correct |
12 |
Correct |
30 ms |
47340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
48236 KB |
Output is correct |
2 |
Correct |
31 ms |
48236 KB |
Output is correct |
3 |
Correct |
31 ms |
48236 KB |
Output is correct |
4 |
Correct |
31 ms |
48236 KB |
Output is correct |
5 |
Correct |
31 ms |
48236 KB |
Output is correct |
6 |
Correct |
31 ms |
48236 KB |
Output is correct |
7 |
Correct |
32 ms |
48236 KB |
Output is correct |
8 |
Correct |
31 ms |
47340 KB |
Output is correct |
9 |
Correct |
31 ms |
47448 KB |
Output is correct |
10 |
Correct |
31 ms |
47980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
56172 KB |
Output is correct |
2 |
Correct |
42 ms |
56172 KB |
Output is correct |
3 |
Correct |
44 ms |
56172 KB |
Output is correct |
4 |
Correct |
45 ms |
56320 KB |
Output is correct |
5 |
Correct |
43 ms |
56172 KB |
Output is correct |
6 |
Correct |
47 ms |
53740 KB |
Output is correct |
7 |
Correct |
42 ms |
54764 KB |
Output is correct |
8 |
Correct |
38 ms |
47724 KB |
Output is correct |
9 |
Correct |
40 ms |
49644 KB |
Output is correct |
10 |
Correct |
43 ms |
54764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
84 ms |
73716 KB |
Output is correct |
2 |
Correct |
69 ms |
73716 KB |
Output is correct |
3 |
Correct |
68 ms |
73716 KB |
Output is correct |
4 |
Correct |
71 ms |
73844 KB |
Output is correct |
5 |
Correct |
79 ms |
73844 KB |
Output is correct |
6 |
Correct |
79 ms |
70900 KB |
Output is correct |
7 |
Correct |
64 ms |
69492 KB |
Output is correct |
8 |
Correct |
54 ms |
48244 KB |
Output is correct |
9 |
Correct |
54 ms |
48244 KB |
Output is correct |
10 |
Correct |
60 ms |
69108 KB |
Output is correct |
11 |
Correct |
65 ms |
73716 KB |
Output is correct |
12 |
Correct |
65 ms |
50420 KB |
Output is correct |