이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define nl '\n'
#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif
template <int md, int base = 133>
struct Hash {
std::vector<int> hsh, ppw;
Hash(const std::string& s, int P = base) : hsh(s.size() + 1, 0), ppw(s.size() + 1, 1) {
for (int i = 0; i < (int) s.size(); i++) {
hsh[i + 1] = ((int64_t) hsh[i] * P + s[i]) % md;
ppw[i + 1] = ((int64_t) ppw[i] * P) % md;
}
}
int get(int l, int r) {
int res = ((int64_t) hsh[r] - (int64_t) hsh[l] * ppw[r - l]) % md;
return res + (res < 0) * md;
}
};
const int md1 = 1000003, md2 = 1000033;
using H1 = Hash<1000003>;
using H2 = Hash<1000033, 311>;
std::vector<int> values[md1];
int cnt[md2];
const int mxN = 3e5 + 1;
std::pair<int, int> hv[mxN];
bool palin[mxN];
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::string s;
std::cin >> s;
int n = s.size();
H1 h1(s);
H2 h2(s);
auto t = s;
std::reverse(t.begin(), t.end());
H1 h1r(t);
H2 h2r(t);
auto get = [&](int l, int r) -> std::pair<int, int> {
return {h1.get(l, r), h2.get(l, r)};
};
auto get_r = [&](int l, int r) -> std::pair<int, int> {
l = n - l;
r = n - r;
std::swap(l, r);
return {h1r.get(l, r), h2r.get(l, r)};
};
int64_t ans = 0;
for (int len = 1; len <= n; len++) {
for (int j = 0; j + len - 1 < n; j++) {
hv[j] = get(j, j + len);
palin[j] = hv[j] == get_r(j, j + len);
if (palin[j]) {
values[hv[j].first].push_back(hv[j].second);
}
}
for (int i = 0; i + len - 1 < n; i++) {
if (!palin[i]) continue;
palin[i] = 0;
for (int v : values[hv[i].first]) {
cnt[v]++;
ans = std::max(ans, (int64_t) cnt[v] * len);
}
for (int v : values[hv[i].first]) {
cnt[v]--;
}
values[hv[i].first].clear();
values[hv[i].first].shrink_to_fit();
}
}
std::cout << ans << nl;
}
# | 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... |