#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
class RollingHash {
public:
long long BASE = 998244353LL;
string S; vector<long long>hash_value1, hash_value2, power;
void init(string str) {
S = str;
power.push_back(1); for (int i = 0; i < str.size(); i++) power.push_back(power[i] * BASE);
hash_value1.push_back(0); for (int i = 0; i < str.size(); i++) hash_value1.push_back(hash_value1[i] * BASE + (str[i] - 'a' + 1));
hash_value2.push_back(0); for (int i = 0; i < str.size(); i++) hash_value2.push_back(hash_value2[i] * BASE + (str[str.size() - 1 - i] - 'a' + 1));
reverse(hash_value2.begin(), hash_value2.end());
}
long long get_val1(long long l, long long r) {
if (r >= S.size()) return 100000000000000000LL + l;
// 区間 [l, r] について
return (hash_value1[r + 1] - hash_value1[l] * power[r - l + 1]);
}
long long get_val2(long long l, long long r) {
// 区間 [l, r] について
if (r >= S.size()) return 100000000000000000LL + l;
return (hash_value2[l] - hash_value2[r + 1] * power[r - l + 1]);
}
bool ispalindrome(long long l, long long r) {
if (l < 0 || r >= S.size()) return false;
long long v1 = get_val1(l, r);
long long v2 = get_val2(l, r);
if (v1 == v2) return true;
return false;
}
};
long long N, A[1 << 19], C[1 << 19], D[1 << 19]; string S;
RollingHash Z;
void SuffixArray() {
for (int i = 0; i < N; i++) A[i] = (S[i] - 'a' + 1);
for (int i = 0; i < 19; i++) {
for (int j = 0; j < N; j++) {
long long v1 = A[j], v2 = 0; if (j + (1 << i) < N) v2 = A[j + (1 << i)];
A[j] = v1 * 1000000LL + v2;
}
vector<pair<long long, int>>vec;
for (int j = 0; j < N; j++) vec.push_back(make_pair(A[j], j));
sort(vec.begin(), vec.end());
int pos = 0;
for (int j = 0; j < N; j++) {
A[vec[j].second] = pos + 1;
if (j < N - 1 && vec[j].first != vec[j + 1].first) pos = j + 1;
}
}
vector<pair<long long, int>> E;
for (int j = 0; j < N; j++) E.push_back(make_pair(A[j], j));
sort(E.begin(), E.end());
for (int j = 0; j < N; j++) A[j] = E[j].second;
}
long long calc(vector<long long>A1, vector<long long>A2, long long BASE) {
vector<long long>V(N + 1, 0);
long long maxn = 0;
for (int i = 0; i < A1.size(); i++) {
for (int j = 0; j <= A1[i]; j++) V[j] += 2LL * j + BASE;
for (int j = 0; j <= N; j++) maxn = max(maxn, V[j]);
if (i == A1.size() - 1) break;
for (int j = A2[i] + 1; j <= N; j++) V[j] = 0;
}
return maxn;
}
long long solve_val1() {
for (int i = 0; i < N; i++) {
int L = 0, R = N, M; C[i] = 0;
for (int j = 0; j < 25; j++) {
M = (L + R) / 2;
int cl = A[i] - M, cr = A[i] + M;
if (Z.ispalindrome(cl, cr) == true) { C[i] = max(C[i], 1LL * M + 1LL); L = M; }
else { R = M; }
}
}
for (int i = 0; i < N - 1; i++) {
int L = 0, R = N, M; D[i] = 0;
int d1 = A[i], d2 = A[i + 1];
for (int j = 0; j < 25; j++) {
M = (L + R) / 2;
if (Z.get_val1(d1, d1 + M - 1) == Z.get_val1(d2, d2 + M - 1)) { D[i] = max(D[i], 1LL * M); L = M; }
else { R = M; }
}
}
vector<long long> B1, B2;
for (int i = 0; i < N; i++) B1.push_back(C[i]);
for (int i = 0; i < N - 1; i++) B2.push_back(D[i]);
return calc(B1, B2, -1);
}
long long solve_val2() {
for (int i = 0; i < N; i++) {
int L = 0, R = N, M; C[i] = 0;
for (int j = 0; j < 25; j++) {
M = (L + R) / 2;
int cl = A[i] - M - 1, cr = A[i] + M;
if (Z.ispalindrome(cl, cr) == true) { C[i] = max(C[i], 1LL * M + 1LL); L = M; }
else { R = M; }
}
}
for (int i = 0; i < N - 1; i++) {
int L = 0, R = N, M; D[i] = 0;
int d1 = A[i], d2 = A[i + 1];
for (int j = 0; j < 25; j++) {
M = (L + R) / 2;
if (Z.get_val1(d1, d1 + M - 1) == Z.get_val1(d2, d2 + M - 1)) { D[i] = max(D[i], 1LL * M); L = M; }
else { R = M; }
}
}
vector<long long> B1, B2;
for (int i = 0; i < N; i++) B1.push_back(C[i]);
for (int i = 0; i < N - 1; i++) B2.push_back(D[i]);
return calc(B1, B2, 0);
}
int main() {
cin >> S; N = S.size();
Z.init(S);
SuffixArray();
long long v1 = solve_val1();
long long v2 = solve_val2();
cout << max(v1, v2) << endl;
return 0;
}
Compilation message
palindrome.cpp: In member function 'void RollingHash::init(std::__cxx11::string)':
palindrome.cpp:15:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
power.push_back(1); for (int i = 0; i < str.size(); i++) power.push_back(power[i] * BASE);
~~^~~~~~~~~~~~
palindrome.cpp:16:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
hash_value1.push_back(0); for (int i = 0; i < str.size(); i++) hash_value1.push_back(hash_value1[i] * BASE + (str[i] - 'a' + 1));
~~^~~~~~~~~~~~
palindrome.cpp:17:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
hash_value2.push_back(0); for (int i = 0; i < str.size(); i++) hash_value2.push_back(hash_value2[i] * BASE + (str[str.size() - 1 - i] - 'a' + 1));
~~^~~~~~~~~~~~
palindrome.cpp: In member function 'long long int RollingHash::get_val1(long long int, long long int)':
palindrome.cpp:21:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (r >= S.size()) return 100000000000000000LL + l;
~~^~~~~~~~~~~
palindrome.cpp: In member function 'long long int RollingHash::get_val2(long long int, long long int)':
palindrome.cpp:27:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (r >= S.size()) return 100000000000000000LL + l;
~~^~~~~~~~~~~
palindrome.cpp: In member function 'bool RollingHash::ispalindrome(long long int, long long int)':
palindrome.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (l < 0 || r >= S.size()) return false;
~~^~~~~~~~~~~
palindrome.cpp: In function 'long long int calc(std::vector<long long int>, std::vector<long long int>, long long int)':
palindrome.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < A1.size(); i++) {
~~^~~~~~~~~~~
palindrome.cpp:73:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i == A1.size() - 1) break;
~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
3 ms |
384 KB |
Output is correct |
13 |
Correct |
3 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
3 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
2 ms |
384 KB |
Output is correct |
22 |
Correct |
3 ms |
384 KB |
Output is correct |
23 |
Correct |
3 ms |
384 KB |
Output is correct |
24 |
Correct |
2 ms |
384 KB |
Output is correct |
25 |
Correct |
3 ms |
384 KB |
Output is correct |
26 |
Correct |
3 ms |
384 KB |
Output is correct |
27 |
Correct |
3 ms |
384 KB |
Output is correct |
28 |
Correct |
2 ms |
384 KB |
Output is correct |
29 |
Correct |
3 ms |
384 KB |
Output is correct |
30 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
31 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
384 KB |
Output is correct |
2 |
Correct |
7 ms |
512 KB |
Output is correct |
3 |
Correct |
8 ms |
384 KB |
Output is correct |
4 |
Correct |
8 ms |
512 KB |
Output is correct |
5 |
Correct |
6 ms |
512 KB |
Output is correct |
6 |
Correct |
7 ms |
512 KB |
Output is correct |
7 |
Correct |
7 ms |
512 KB |
Output is correct |
8 |
Correct |
8 ms |
512 KB |
Output is correct |
9 |
Correct |
9 ms |
512 KB |
Output is correct |
10 |
Incorrect |
8 ms |
384 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
285 ms |
1328 KB |
Output is correct |
2 |
Correct |
266 ms |
1420 KB |
Output is correct |
3 |
Correct |
284 ms |
1292 KB |
Output is correct |
4 |
Correct |
295 ms |
1360 KB |
Output is correct |
5 |
Correct |
288 ms |
1360 KB |
Output is correct |
6 |
Correct |
268 ms |
1516 KB |
Output is correct |
7 |
Correct |
259 ms |
1392 KB |
Output is correct |
8 |
Correct |
277 ms |
1484 KB |
Output is correct |
9 |
Incorrect |
284 ms |
1416 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1061 ms |
9536 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1082 ms |
28768 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |