이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned;
using i16 = short;
using u16 = unsigned short;
using ld = long double;
using ii = pair<int, int>;
const int mod[2] = {67557961, 1'000'000'009};
const int base[2] = {3468547, 752747959};
struct Hash {
vector<int> h[2], pt[2];
int n;
Hash() {}
Hash(string& s) {
n = s.size();
for(int i = 0; i < 2; ++i) {
h[i].resize(n + 1);
pt[i].resize(n + 1);
h[i][0] = 0, pt[i][0] = 1;
for(int j = 1; j <= n; ++j) {
pt[i][j] = (i64)pt[i][j - 1] * base[i] % mod[i];
h[i][j] = (h[i][j - 1] + pt[i][j] * (s[j - 1] - 'a' + 1ll)) % mod[i];
}
}
}
int hash(int k, int l, int r) {
i64 x = h[k][r] - h[k][l - 1];
if(x < 0) x += mod[k];
return x * pt[k][n - l] % mod[k];
}
ii hash(int l, int r) {
++l, ++r;
return ii(hash(0, l, r), hash(1, l, r));
}
};
string s;
int l, r, n;
Hash h;
vector<int> d1, d2;
i64 f(int m) {
map<ii, int> cnt;
i64 ans = 0;
if(m & 1) {
for(int i = 0; i < n; ++i) {
if(2 * d1[i] + 1 < m) continue;
ans = max(ans, ++cnt[h.hash(i - d1[i], i + d1[i])] * (i64)m);
}
} else {
for(int i = 0, k; i < n; ++i) {
if(2 * d2[i] < m) continue;
ans = max(ans, ++cnt[h.hash(i - d2[i], i + d2[i] - 1)] * (i64)m);
}
}
return ans;
}
void solve() {
cin >> s;
h = Hash(s);
l = 0, r = -1, n = s.size();
d1.assign(n, 1);
d2.assign(n, 0);
for(int i = 0; i < n; ++i) {
if(i <= r) {
d1[i] = min(d1[l + r - i], r - i + 1);
d2[i] = min(d2[l + r - i + 1], r - i + 1);
}
while(i + d1[i] < n && i - d1[i] >= 0 && s[i - d1[i]] == s[i + d1[i]]) ++d1[i];
while(i + d2[i] < n && i - d2[i] - 1 >= 0 && s[i - d2[i] - 1] == s[i + d2[i]]) ++d2[i];
if(r < i + d2[i] - 1) l = i - d2[i], r = i + d2[i] - 1;
if(r < i + d1[i] - 1) l = i - d1[i] + 1, r = i + d1[i] - 1;
}
l = 1, r = n;
while(l < r) {
int mid = (l + r) / 2;
if(f(mid) > f(mid + 1)) r = mid;
else l = mid + 1;
}
cout << f(r) << '\n';
}
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) solve();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
palindrome.cpp: In function 'i64 f(int)':
palindrome.cpp:58:18: warning: unused variable 'k' [-Wunused-variable]
58 | for(int i = 0, k; i < n; ++i) {
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |