#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
typedef long long ll;
using namespace std;
const int maxn = 3e5 + 5, abc = 26;
//const int maxn = 15, abc = 26;
struct node
{
int nx[abc], len, link, cnt; // hrany dopredu, dlzka, spatna hrana, pocet kratov kedy som videla tento palindrom
} vr[maxn];
string s;
int suf, nd = 2;
void add(int i, int ch)
{
while (i - vr[suf].len - 1 < 0 || s[i - vr[suf].len - 1] != s[i])
{
suf = vr[suf].link;
}
if (vr[suf].nx[ch])
{
suf = vr[suf].nx[ch];
vr[suf].cnt++;
return;
}
nd++;
vr[nd].len = vr[suf].len + 2;
vr[suf].nx[ch] = nd;
int j = vr[suf].link;
suf = nd;
vr[suf].cnt++;
if (vr[suf].len == 1)
{
vr[suf].link = 2;
return;
}
while (i - vr[j].len - 1 < 0 || s[i - vr[j].len - 1] != s[i])
{
j = vr[j].link;
}
vr[suf].link = vr[j].nx[ch];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
vr[1].link = 1, vr[1].len = -1;
vr[2].link = 1, vr[2].len = 0;
suf = 2;
cin >> s;
int n = s.size();
for (int i = 0; i < n; i++)
add(i, s[i] - 'a');
ll ans = 0;
for (int i = nd; i > 0; i--)
{
//cout << vr[i].cnt << "*" << vr[i].len << "\n";
ans = max(ans, vr[i].cnt * 1ll * vr[i].len);
vr[vr[i].link].cnt += vr[i].cnt;
}
cout << ans << "\n";
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
324 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
204 KB |
Output is correct |
| 13 |
Correct |
0 ms |
204 KB |
Output is correct |
| 14 |
Correct |
0 ms |
328 KB |
Output is correct |
| 15 |
Correct |
0 ms |
204 KB |
Output is correct |
| 16 |
Correct |
0 ms |
204 KB |
Output is correct |
| 17 |
Correct |
1 ms |
204 KB |
Output is correct |
| 18 |
Correct |
1 ms |
204 KB |
Output is correct |
| 19 |
Correct |
0 ms |
332 KB |
Output is correct |
| 20 |
Correct |
0 ms |
332 KB |
Output is correct |
| 21 |
Correct |
0 ms |
332 KB |
Output is correct |
| 22 |
Correct |
1 ms |
204 KB |
Output is correct |
| 23 |
Correct |
1 ms |
332 KB |
Output is correct |
| 24 |
Correct |
1 ms |
204 KB |
Output is correct |
| 25 |
Correct |
1 ms |
204 KB |
Output is correct |
| 26 |
Correct |
1 ms |
312 KB |
Output is correct |
| 27 |
Correct |
1 ms |
332 KB |
Output is correct |
| 28 |
Correct |
1 ms |
204 KB |
Output is correct |
| 29 |
Correct |
1 ms |
332 KB |
Output is correct |
| 30 |
Correct |
1 ms |
204 KB |
Output is correct |
| 31 |
Correct |
1 ms |
204 KB |
Output is correct |
| 32 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
316 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1480 KB |
Output is correct |
| 2 |
Correct |
1 ms |
1476 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1484 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1484 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1484 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1480 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1484 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1100 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
11980 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11892 KB |
Output is correct |
| 3 |
Correct |
8 ms |
11980 KB |
Output is correct |
| 4 |
Correct |
9 ms |
11980 KB |
Output is correct |
| 5 |
Correct |
11 ms |
11980 KB |
Output is correct |
| 6 |
Correct |
7 ms |
8780 KB |
Output is correct |
| 7 |
Correct |
7 ms |
10188 KB |
Output is correct |
| 8 |
Correct |
3 ms |
716 KB |
Output is correct |
| 9 |
Correct |
4 ms |
3276 KB |
Output is correct |
| 10 |
Correct |
7 ms |
10188 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
35020 KB |
Output is correct |
| 2 |
Correct |
25 ms |
34980 KB |
Output is correct |
| 3 |
Correct |
24 ms |
35016 KB |
Output is correct |
| 4 |
Correct |
25 ms |
35028 KB |
Output is correct |
| 5 |
Correct |
26 ms |
35020 KB |
Output is correct |
| 6 |
Correct |
22 ms |
31228 KB |
Output is correct |
| 7 |
Correct |
22 ms |
29260 KB |
Output is correct |
| 8 |
Correct |
7 ms |
1364 KB |
Output is correct |
| 9 |
Correct |
7 ms |
1236 KB |
Output is correct |
| 10 |
Correct |
26 ms |
28844 KB |
Output is correct |
| 11 |
Correct |
22 ms |
35028 KB |
Output is correct |
| 12 |
Correct |
8 ms |
4184 KB |
Output is correct |
