#include <bits/stdc++.h>
using namespace std;
const int N = 10004;
const long long P = 31;
int n;
char aa[N], a[N];
long long ast[N];
long long p[N], s[N];
bool pal(int l, int r)
{
return (p[r] - p[l - 1]) * ast[n - r] == (s[l] - s[r + 1]) * ast[l - 1];
}
unordered_map<long long, int> b[N];
int main()
{
cin >> aa;
n = strlen(aa);
for (int i = 1; i <= n; ++i)
a[i] = aa[i - 1];
ast[0] = 1;
for (int i = 1; i <= n; ++i)
ast[i] = ast[i - 1] * P;
for (int i = 1; i <= n; ++i)
p[i] = p[i - 1] + ast[i - 1] * (a[i] - 'a' + 1);
for (int i = n; i >= 1; --i)
s[i] = s[i + 1] + ast[n - i] * (a[i] - 'a' + 1);
for (int l = 1; l <= n; ++l)
{
for (int r = l; r <= n; ++r)
{
b[(r - l + 1)][(p[r] - p[l - 1]) * ast[n - r]]++;
}
}
int ans = 0;
for (int l = 1; l <= n; ++l)
{
int pos = 0;
for (int r = l; r <= n; ++r)
{
if (pal(l, r))
ans = max(ans, b[r - l + 1][(p[r] - p[l - 1]) * ast[n - r]] * (r - l + 1));
}
}
cout << ans << endl;
return 0;
}
Compilation message
palindrome.cpp: In function 'int main()':
palindrome.cpp:46:13: warning: unused variable 'pos' [-Wunused-variable]
int pos = 0;
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
896 KB |
Output is correct |
2 |
Correct |
2 ms |
896 KB |
Output is correct |
3 |
Correct |
3 ms |
896 KB |
Output is correct |
4 |
Correct |
3 ms |
896 KB |
Output is correct |
5 |
Correct |
2 ms |
896 KB |
Output is correct |
6 |
Correct |
3 ms |
896 KB |
Output is correct |
7 |
Correct |
14 ms |
896 KB |
Output is correct |
8 |
Correct |
3 ms |
896 KB |
Output is correct |
9 |
Correct |
3 ms |
896 KB |
Output is correct |
10 |
Correct |
2 ms |
896 KB |
Output is correct |
11 |
Correct |
2 ms |
896 KB |
Output is correct |
12 |
Correct |
3 ms |
896 KB |
Output is correct |
13 |
Correct |
3 ms |
896 KB |
Output is correct |
14 |
Correct |
2 ms |
896 KB |
Output is correct |
15 |
Correct |
3 ms |
896 KB |
Output is correct |
16 |
Correct |
2 ms |
896 KB |
Output is correct |
17 |
Correct |
4 ms |
896 KB |
Output is correct |
18 |
Correct |
3 ms |
896 KB |
Output is correct |
19 |
Correct |
3 ms |
896 KB |
Output is correct |
20 |
Correct |
3 ms |
896 KB |
Output is correct |
21 |
Correct |
4 ms |
1024 KB |
Output is correct |
22 |
Correct |
3 ms |
1024 KB |
Output is correct |
23 |
Correct |
4 ms |
896 KB |
Output is correct |
24 |
Correct |
3 ms |
1024 KB |
Output is correct |
25 |
Correct |
3 ms |
896 KB |
Output is correct |
26 |
Correct |
3 ms |
1024 KB |
Output is correct |
27 |
Correct |
4 ms |
1024 KB |
Output is correct |
28 |
Correct |
4 ms |
1024 KB |
Output is correct |
29 |
Correct |
4 ms |
1152 KB |
Output is correct |
30 |
Correct |
4 ms |
1152 KB |
Output is correct |
31 |
Correct |
4 ms |
1152 KB |
Output is correct |
32 |
Correct |
4 ms |
1024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
1024 KB |
Output is correct |
2 |
Correct |
150 ms |
12508 KB |
Output is correct |
3 |
Correct |
21 ms |
1024 KB |
Output is correct |
4 |
Correct |
273 ms |
20344 KB |
Output is correct |
5 |
Correct |
25 ms |
1024 KB |
Output is correct |
6 |
Correct |
25 ms |
1024 KB |
Output is correct |
7 |
Correct |
227 ms |
15428 KB |
Output is correct |
8 |
Correct |
18 ms |
1024 KB |
Output is correct |
9 |
Correct |
289 ms |
20972 KB |
Output is correct |
10 |
Correct |
305 ms |
22492 KB |
Output is correct |
11 |
Correct |
342 ms |
22392 KB |
Output is correct |
12 |
Incorrect |
250 ms |
17244 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1073 ms |
2048 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
4 ms |
1536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
1536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |