#include <bits/stdc++.h>
#define nl '\n'
#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif
namespace hash {
using u64 = uint64_t;
using u32 = uint32_t;
constexpr int kSeed = -1; // change this to fixed seed for predictable base
constexpr u64 kAlpha = 1000000007; // the value is from 0 -> kAlphabet - 1
constexpr u64 kMod = (1ULL << 61) - 1;
static_assert(kMod - kAlpha > 2);
// randomly getting an odd base from kAlpha + 1 -> kMod - 1
u64 get_random_base(u64 not_this = -1) {
std::mt19937_64 h_rng(
kSeed == -1
? std::chrono::high_resolution_clock::now().time_since_epoch().count()
: kSeed);
auto rd = std::uniform_int_distribution<u64>(kAlpha + 2, kMod - 1);
u64 base = rd(h_rng);
base -= base % 2 == 0;
while (base == not_this) {
base = rd(h_rng);
base -= base % 2 == 0;
}
return base;
}
u64 mul(u64 a, u64 b) {
u64 l1 = (u32)a, h1 = a >> 32, l2 = (u32)b, h2 = b >> 32;
u64 l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
u64 ret = (l & kMod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
ret = (ret & kMod) + (ret >> 61);
ret = (ret & kMod) + (ret >> 61);
return ret - 1;
}
u64 add(u64 a, u64 b) { return a += b, a -= (a >= kMod) * kMod; }
u64 sub(u64 a, u64 b) { return a + (a < b) * kMod - b; }
u64 p = get_random_base(), q = get_random_base(p);
std::vector<u64> pp(1, 1), qq(1, 1);
void ensure_pp_size(int size) {
while ((int)pp.size() < size) pp.emplace_back(mul(pp.back(), p));
}
void ensure_qq_size(int size) {
while ((int)qq.size() < size) qq.emplace_back(mul(qq.back(), q));
}
struct FwdHash {
std::vector<u64> hf;
FwdHash() = default;
template <typename String>
FwdHash(const String& s) : hf(s.size() + 1) {
ensure_pp_size(s.size() + 1);
for (int i = 0; i < (int)s.size(); i++) {
hf[i + 1] = add(mul(hf[i], p), s[i] + 1);
}
}
int size() const { return hf.size() - 1; }
// NOTE: [l, r)
u64 get_fwd(int l, int r) const { return sub(hf[r], mul(hf[l], pp[r - l])); }
int operator[](int index) const { return get_fwd(index, index + 1) - 1; }
};
struct FBHash : FwdHash {
std::vector<u64> hb;
FBHash() = default;
template <typename String>
FBHash(const String& s) : FwdHash(s), hb(s.size() + 1) {
for (int i = s.size() - 1; i >= 0; i--) {
hb[i] = add(mul(hb[i + 1], p), s[i] + 1);
}
}
// NOTE: [l, r)
u64 get_bwd(int l, int r) const { return sub(hb[l], mul(hb[r], pp[r - l])); }
};
struct Hash2D {
std::vector<std::vector<u64>> h;
Hash2D() = default;
template <typename String2D>
Hash2D(const String2D& s)
: h(s.size() + 1, std::vector<u64>(s[0].size() + 1)) {
int n = s.size();
int m = s[0].size();
ensure_pp_size(n + 1);
ensure_qq_size(m + 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
h[i + 1][j + 1] = add(mul(h[i + 1][j], q), s[i][j] + 1);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
h[i][j] = add(mul(h[i - 1][j], p), h[i][j]);
}
}
}
// NOTE: [x, u) * [y, v)
u64 get(int x, int y, int u, int v) {
auto res = sub(h[u][v], mul(h[x][v], pp[u - x]));
res = sub(res, mul(h[u][y], qq[v - y]));
return add(res, mul(mul(h[x][y], pp[u - x]), qq[v - y]));
}
};
// NOTE: [l1, h1.size()) and [l2, h2.size())
int longest_common_prefix(const FwdHash& h1, const FwdHash& h2, int l1,
int l2) {
int lb = 0, rb = std::min(h1.size() - l1, h2.size() - l2) + 1;
while (lb < rb - 1) {
int mb = (lb + rb) / 2;
if (h1.get_fwd(l1, l1 + mb) == h2.get_fwd(l2, l2 + mb)) {
lb = mb;
} else {
rb = mb;
}
}
return lb;
}
// NOTE: [0, r1) and [0, r2)
int longest_common_suffix(const FwdHash& h1, const FwdHash& h2, int r1,
int r2) {
int lb = 0, rb = std::min(r1, r2) + 1;
while (lb < rb - 1) {
int mb = (lb + rb) / 2;
if (h1.get_fwd(r1 - mb, r1) == h2.get_fwd(r2 - mb, r2)) {
lb = mb;
} else {
rb = mb;
}
}
return lb;
}
// NOTE: [l1, r1) and [l2, r2)
bool is_smaller(const FwdHash& h1, const FwdHash& h2, int l1, int r1, int l2,
int r2) {
int lcp = longest_common_prefix(h1, h2, l1, l2);
int len1 = r1 - l1;
int len2 = r2 - l2;
int min_len = std::min(len1, len2);
return lcp >= min_len ? len1 < len2 : h1[l1 + lcp] < h2[l2 + lcp];
}
} // namespace hash
using hash::FBHash;
using hash::FwdHash;
using hash::Hash2D;
namespace suffarr {
std::vector<int> sa_is(const std::vector<int> &s, int upper) {
int n = int(s.size());
if (n == 0) return {};
if (n == 1) return {0};
if (n == 2) {
if (s[0] < s[1]) {
return {0, 1};
} else {
return {1, 0};
}
}
std::vector<int> sa(n);
std::vector<bool> ls(n);
for (int i = n - 2; i >= 0; i--) {
ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
}
std::vector<int> sum_l(upper + 1), sum_s(upper + 1);
for (int i = 0; i < n; i++) {
if (!ls[i]) {
sum_s[s[i]]++;
} else {
sum_l[s[i] + 1]++;
}
}
for (int i = 0; i <= upper; i++) {
sum_s[i] += sum_l[i];
if (i < upper) sum_l[i + 1] += sum_s[i];
}
auto induce = [&](const std::vector<int> &lms) {
std::fill(sa.begin(), sa.end(), -1);
std::vector<int> buf(upper + 1);
std::copy(sum_s.begin(), sum_s.end(), buf.begin());
for (auto d : lms) {
if (d == n) continue;
sa[buf[s[d]]++] = d;
}
std::copy(sum_l.begin(), sum_l.end(), buf.begin());
sa[buf[s[n - 1]]++] = n - 1;
for (int i = 0; i < n; i++) {
int v = sa[i];
if (v >= 1 && !ls[v - 1]) {
sa[buf[s[v - 1]]++] = v - 1;
}
}
std::copy(sum_l.begin(), sum_l.end(), buf.begin());
for (int i = n - 1; i >= 0; i--) {
int v = sa[i];
if (v >= 1 && ls[v - 1]) {
sa[--buf[s[v - 1] + 1]] = v - 1;
}
}
};
std::vector<int> lms_map(n + 1, -1);
int m = 0;
for (int i = 1; i < n; i++) {
if (!ls[i - 1] && ls[i]) {
lms_map[i] = m++;
}
}
std::vector<int> lms;
lms.reserve(m);
for (int i = 1; i < n; i++) {
if (!ls[i - 1] && ls[i]) {
lms.push_back(i);
}
}
induce(lms);
if (m) {
std::vector<int> sorted_lms;
sorted_lms.reserve(m);
for (int v : sa) {
if (lms_map[v] != -1) sorted_lms.push_back(v);
}
std::vector<int> rec_s(m);
int rec_upper = 0;
rec_s[lms_map[sorted_lms[0]]] = 0;
for (int i = 1; i < m; i++) {
int l = sorted_lms[i - 1], r = sorted_lms[i];
int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
bool same = true;
if (end_l - l != end_r - r) {
same = false;
} else {
while (l < end_l) {
if (s[l] != s[r]) {
break;
}
l++;
r++;
}
if (l == n || s[l] != s[r]) same = false;
}
if (!same) rec_upper++;
rec_s[lms_map[sorted_lms[i]]] = rec_upper;
}
auto rec_sa = sa_is(rec_s, rec_upper);
for (int i = 0; i < m; i++) {
sorted_lms[i] = lms[rec_sa[i]];
}
induce(sorted_lms);
}
return sa;
}
std::vector<int> suffix_array(const std::vector<int> &s, int upper) {
assert(0 <= upper);
for (int d : s) {
assert(0 <= d && d <= upper);
}
auto sa = suffarr::sa_is(s, upper);
return sa;
}
template <class T>
std::vector<int> suffix_array(const std::vector<T> &s) {
int n = int(s.size());
std::vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int l, int r) { return s[l] < s[r]; });
std::vector<int> s2(n);
int now = 0;
for (int i = 0; i < n; i++) {
if (i && s[idx[i - 1]] != s[idx[i]]) now++;
s2[idx[i]] = now;
}
return suffarr::sa_is(s2, now);
}
std::vector<int> suffix_array(const std::string &s) {
int n = int(s.size());
std::vector<int> s2(n);
for (int i = 0; i < n; i++) {
s2[i] = s[i];
}
return suffarr::sa_is(s2, 255);
}
template <class T>
std::vector<int> lcp_array(const std::vector<T> &s,
const std::vector<int> &sa) {
int n = int(s.size());
assert(n >= 1);
std::vector<int> rnk(n);
for (int i = 0; i < n; i++) {
rnk[sa[i]] = i;
}
std::vector<int> lcp(n - 1);
int h = 0;
for (int i = 0; i < n; i++) {
if (h > 0) h--;
if (rnk[i] == 0) continue;
int j = sa[rnk[i] - 1];
for (; j + h < n && i + h < n; h++) {
if (s[j + h] != s[i + h]) break;
}
lcp[rnk[i] - 1] = h;
}
return lcp;
}
std::vector<int> lcp_array(const std::string &s, const std::vector<int> &sa) {
int n = int(s.size());
std::vector<int> s2(n);
for (int i = 0; i < n; i++) {
s2[i] = s[i];
}
return lcp_array(s2, sa);
}
// Count keyword occurence in str
// Complexity: O(min(|str|, |keyword|) * lg |str|)
int count_keyword_occurence(const std::string &str,
const std::vector<int> &suffarr,
const std::string &keyword) {
const int n = str.size(), m = keyword.size();
assert(n == (int) suffarr.size());
if (n < m) return 0;
auto f1 = [&](int h) {
for (int j = 0; h + j < n and j < m; j++) {
if (str[h + j] < keyword[j]) return true;
if (str[h + j] > keyword[j]) return false;
}
return n - h < m;
};
auto f2 = [&](int h) {
for (int j = 0; h + j < n and j < m; j++) {
// if (str[h + j] < keyword[j]) return true;
if (str[h + j] > keyword[j]) return false;
}
return true;
};
const auto L = std::partition_point(suffarr.begin(), suffarr.end(), f1);
const auto R = std::partition_point(L, suffarr.end(), f2);
return std::distance(L, R);
// return std::vector<int>(L, R); // if you need occurence positions
}
} // namespace suffarr
using suffarr::suffix_array;
using suffarr::lcp_array;
template<typename T, typename F>
struct SparseTable {
std::vector<std::vector<T>> t;
SparseTable() {}
SparseTable(const std::vector<T>& a) : t(std::__lg(a.size()) + 1, std::vector<T>(a)) {
for (int k = 0; k + 1 < (int) t.size(); k++)
for (int i = 0; i + (1 << k) < (int) a.size(); i++)
t[k + 1][i] = F()(t[k][i], t[k][i + (1 << k)]);
}
// NOTE: [l, r)
T query(int l, int r) {
int k = std::__lg(r - l);
return F()(t[k][l], t[k][r - (1 << k)]);
}
};
template<typename T>
struct MinMerge {
T operator()(const T& a, const T& b) {
return std::min<T>(a, b);
}
};
template <typename T>
using MinSparseTable = SparseTable<T, MinMerge<T>>;
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::string s;
std::cin >> s;
int n = s.size();
FBHash hasher(s);
// we get all unique palindromes
struct Palindrome {
int m1, m2, len;
};
std::set<uint64_t> palin_hashes;
std::vector<Palindrome> unique_palins;
auto is_palindrome = [&](int l, int r) -> bool {
return hasher.get_fwd(l, r) == hasher.get_bwd(l, r);
};
auto add_all = [&](int m1, int m2) {
int lb = 0, rb = std::min(m1 + 1, n - m2) + 1;
while (lb < rb - 1) {
int mb = (lb + rb) / 2;
if (is_palindrome(m1 - mb + 1, m2 + mb)) {
lb = mb;
} else {
rb = mb;
}
}
int len = lb;
while (len > 0) {
auto hsh = hasher.get_fwd(m1 - len + 1, m2 + len);
auto it = palin_hashes.insert(hsh);
if (it.second == false) break;
unique_palins.push_back({m1, m2, len});
len--;
}
};
for (int i = 0; i < n; i++) {
add_all(i, i);
if (i + 1 < n) {
add_all(i, i + 1);
}
}
auto sa = suffix_array(s);
auto lcp = lcp_array(s, sa);
std::vector<int> pos(n);
for (int i = 0; i < n; i++) {
pos[sa[i]] = i;
}
MinSparseTable<int> tab(lcp);
dbg(sa);
dbg(lcp);
/*
2 bbbc
1 bbc
0 bc
c
*/
auto count_occurrence = [&](int l, int r) -> int {
int len = r - l;
l = pos[l];
int upper = l;
int lb = 0, rb = l - 1;
while (lb <= rb) {
int mb = (lb + rb) / 2;
int val = tab.query(mb, l);
if (val >= len) {
upper = mb;
rb = mb - 1;
} else {
lb = mb + 1;
}
}
int lower = l;
lb = l + 1, rb = n - 1;
while (lb <= rb) {
int mb = (lb + rb) / 2;
int val = tab.query(l, mb);
if (val >= len) {
lower = mb;
lb = mb + 1;
} else {
rb = mb - 1;
}
}
dbg(lower, upper);
return lower - upper + 1;
};
// b, b, b, c
int64_t ans = -1;
for (auto [m1, m2, len] : unique_palins) {
int lb = m1 - len + 1, rb = m2 + len;
len = rb - lb;
dbg(lb, rb);
ans = std::max(ans, (int64_t) len * count_occurrence(lb, rb));
}
std::cout << ans << nl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Correct |
0 ms |
348 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Correct |
0 ms |
344 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
0 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
348 KB |
Output is correct |
| 19 |
Correct |
1 ms |
600 KB |
Output is correct |
| 20 |
Correct |
0 ms |
348 KB |
Output is correct |
| 21 |
Correct |
0 ms |
348 KB |
Output is correct |
| 22 |
Correct |
0 ms |
348 KB |
Output is correct |
| 23 |
Correct |
0 ms |
348 KB |
Output is correct |
| 24 |
Correct |
1 ms |
348 KB |
Output is correct |
| 25 |
Correct |
0 ms |
348 KB |
Output is correct |
| 26 |
Correct |
1 ms |
344 KB |
Output is correct |
| 27 |
Correct |
0 ms |
348 KB |
Output is correct |
| 28 |
Correct |
0 ms |
348 KB |
Output is correct |
| 29 |
Correct |
0 ms |
348 KB |
Output is correct |
| 30 |
Correct |
0 ms |
348 KB |
Output is correct |
| 31 |
Correct |
0 ms |
348 KB |
Output is correct |
| 32 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
488 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
604 KB |
Output is correct |
| 8 |
Correct |
1 ms |
604 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
424 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
1876 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1876 KB |
Output is correct |
| 3 |
Correct |
7 ms |
1884 KB |
Output is correct |
| 4 |
Correct |
7 ms |
1884 KB |
Output is correct |
| 5 |
Correct |
7 ms |
1884 KB |
Output is correct |
| 6 |
Correct |
7 ms |
1884 KB |
Output is correct |
| 7 |
Correct |
7 ms |
1880 KB |
Output is correct |
| 8 |
Correct |
5 ms |
1368 KB |
Output is correct |
| 9 |
Correct |
5 ms |
1372 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1748 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
108 ms |
17264 KB |
Output is correct |
| 2 |
Correct |
98 ms |
17160 KB |
Output is correct |
| 3 |
Correct |
98 ms |
16940 KB |
Output is correct |
| 4 |
Correct |
102 ms |
16980 KB |
Output is correct |
| 5 |
Correct |
91 ms |
17672 KB |
Output is correct |
| 6 |
Correct |
93 ms |
16400 KB |
Output is correct |
| 7 |
Correct |
90 ms |
16628 KB |
Output is correct |
| 8 |
Correct |
51 ms |
11272 KB |
Output is correct |
| 9 |
Correct |
61 ms |
12812 KB |
Output is correct |
| 10 |
Correct |
85 ms |
16216 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
411 ms |
54324 KB |
Output is correct |
| 2 |
Correct |
367 ms |
55976 KB |
Output is correct |
| 3 |
Correct |
422 ms |
54784 KB |
Output is correct |
| 4 |
Correct |
409 ms |
55336 KB |
Output is correct |
| 5 |
Correct |
527 ms |
57892 KB |
Output is correct |
| 6 |
Correct |
345 ms |
55860 KB |
Output is correct |
| 7 |
Correct |
318 ms |
52680 KB |
Output is correct |
| 8 |
Correct |
167 ms |
37996 KB |
Output is correct |
| 9 |
Correct |
165 ms |
37064 KB |
Output is correct |
| 10 |
Correct |
440 ms |
51400 KB |
Output is correct |
| 11 |
Correct |
389 ms |
55240 KB |
Output is correct |
| 12 |
Correct |
176 ms |
38912 KB |
Output is correct |
