이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) { return l + rnd() % (r - l + 1); }
struct SUFFIX_ARRAY{
vector<int> sort_cyclic_shifts(string const& s) {
int n = s.size();
const int alphabet = 256;
vector<int> p(n), c(n), cnt(max(alphabet, n), 0);
for (int i = 0; i < n; i++) cnt[s[i]]++;
for (int i = 1; i < alphabet; i++) cnt[i] += cnt[i - 1];
for (int i = 0; i < n; i++) p[--cnt[s[i]]] = i;
c[p[0]] = 0;
int classes = 1;
for (int i = 1; i < n; i++) {
if (s[p[i]] != s[p[i-1]]) classes++;
c[p[i]] = classes - 1;
}
vector<int> pn(n), cn(n);
for (int h = 0; (1 << h) < n; ++h) {
for (int i = 0; i < n; i++) {
pn[i] = p[i] - (1 << h);
if (pn[i] < 0) pn[i] += n;
}
fill(cnt.begin(), cnt.begin() + classes, 0);
for (int i = 0; i < n; i++) cnt[c[pn[i]]]++;
for (int i = 1; i < classes; i++) cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; i--) p[--cnt[c[pn[i]]]] = pn[i];
cn[p[0]] = 0;
classes = 1;
for (int i = 1; i < n; i++) {
pair<int, int> cur = {c[p[i]], c[(p[i] + (1 << h)) % n]};
pair<int, int> prev = {c[p[i-1]], c[(p[i-1] + (1 << h)) % n]};
if (cur != prev) ++classes;
cn[p[i]] = classes - 1;
}
c.swap(cn);
}
return p;
}
vector<int> suffix_array(string s) {
s += "$";
vector<int> sorted_shifts = sort_cyclic_shifts(s);
sorted_shifts.erase(sorted_shifts.begin());
return sorted_shifts;
}
vector<int> kasai(string txt, vector<int> suffixArr) {
int n = suffixArr.size();
vector<int> lcp(n, 0);
vector<int> invSuff(n, 0);
for (int i = 0; i < n; i++) invSuff[suffixArr[i]] = i;
int k = 0;
for (int i = 0; i < n; i++) {
if (invSuff[i] == n - 1) {
k = 0;
continue;
}
int j = suffixArr[invSuff[i]+1];
while (i + k < n && j + k < n && txt[i + k] == txt[j + k]) k++;
lcp[invSuff[i]] = k;
if (k > 0) k--;
}
return lcp;
}
} T;
const int MAXN = 3e5 + 5;
const int MOD = 1e9 + 7;
int N, f[20][MAXN], pos[MAXN], Hash[2 * MAXN], Pow[2 * MAXN];
int suff[MAXN];
int get_lcp(int l, int r) {
if (l == r) return N - l + 1;
l = pos[l]; r = pos[r];
if (l > r) swap(l, r); r--;
int k = 31 - __builtin_clz(r - l + 1);
return min(f[k][l], f[k][r - (1 << k) + 1]);
}
void Construct(string s) {
N = s.size();
vector <int> sa = T.suffix_array(s);
vector <int> lcp = T.kasai(s, sa);
REP(i, N) {
pos[sa[i] + 1] = i + 1;
f[0][i + 1] = lcp[i];
suff[i + 1] = sa[i] + 1;
}
for (int i = 1; (1 << i) <= N; i++)
for (int j = 1; j <= N - (1 << i) + 1; j++)
f[i][j] = min(f[i - 1][j], f[i - 1][j + (1 << i - 1)]);
}
void Hashing(string s) {
string t = s;
reverse(ALL(t));
s = ' ' + s + t;
Pow[0] = 1;
FOR(i, 1, 2 * N) {
Hash[i] = (1ll * Hash[i - 1] * 31 + s[i] - 'a') % MOD;
Pow[i] = 31ll * Pow[i - 1] % MOD;
}
}
int code(int l, int r) {
return (Hash[r] - 1ll * Hash[l - 1] * Pow[r - l + 1] % MOD + MOD) % MOD;
}
bool is_palindrome(int l, int r) {
int u = l + r >> 1;
int v = u + 1;
if ((r - l + 1) & 1) v--;
r = N - r + 1 + N;
v = N - v + 1 + N;
return code(l, u) == code(r, v);
}
unordered_set <int> dd[MAXN];
vector <pair <int, int>> Distinct_palindrome_substring(string s) {
vector <pair <int, int>> ans;
FOR(i, 1, N) {
int l = 0, r = min(i, N - i + 1);
while (r - l > 1) {
int mid = l + r >> 1;
if (is_palindrome(i - mid, i + mid)) l = mid;
else r = mid;
}
int len = l;
l = i - len, r = i + len;
while (r >= l) {
if (dd[r - l + 1].find(code(l, r)) != dd[r - l + 1].end()) break;
dd[r - l + 1].insert(code(l, r));
ans.emplace_back(l, r);
l++; r--;
}
if (i < N && s[i] == s[i + 1]) {
int l = 0, r = min(i, N - i);
while (r - l > 1) {
int mid = l + r >> 1;
if (is_palindrome(i - mid, i + mid + 1)) l = mid;
else r = mid;
}
len = l;
l = i - len, r = i + 1 + len;
while (r >= l) {
if (dd[r - l + 1].find(code(l, r)) != dd[r - l + 1].end()) break;
dd[r - l + 1].insert(code(l, r));
ans.emplace_back(l, r);
l++; r--;
}
}
}
return ans;
}
bool Lower_bound(int l, int r, int mid, string &s) {
int len = get_lcp(l, mid);
len = min(len, r - l + 1);
if (len == r - l + 1) return true;
if (len == N - mid + 1) return false;
return s[l + len] < s[mid + len];
}
bool Upper_bound(int l, int r, int mid, string &s) {
int len = get_lcp(l, mid);
len = min(len, r - l + 1);
if (len == r - l + 1) return false;
if (len == N - mid + 1) return false;
return s[l + len] < s[mid + len];
}
int count_occurences(int l, int r, string &s) {
int L = 0, R = N + 1;
while (R - L > 1) {
int mid = L + R >> 1;
if (Lower_bound(l, r, suff[mid], s)) R = mid;
else L = mid;
}
int u = R, v = 0;
L = 0, R = N + 1;
while (R - L > 1) {
int mid = L + R >> 1;
if (Upper_bound(l, r, suff[mid], s)) R = mid;
else L = mid;
}
v = R - 1;
return v - u + 1;
}
signed main(void) {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
//int T; cin >> T; while (T--)
string s; cin >> s;
Construct(s);
Hashing(s);
s = ' ' + s;
auto sets = Distinct_palindrome_substring(s);
long long ans = 0;
for (auto x : sets) {
ans = max(ans, count_occurences(x.first, x.second, s) * (x.second - x.first + 1ll));
}
cout << ans;
cerr << "Time elapsed: " << TIME << " s.\n";
return (0 ^ 0);
}
컴파일 시 표준 에러 (stderr) 메시지
palindrome.cpp: In function 'int get_lcp(int, int)':
palindrome.cpp:88:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
88 | if (l > r) swap(l, r); r--;
| ^~
palindrome.cpp:88:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
88 | if (l > r) swap(l, r); r--;
| ^
palindrome.cpp: In function 'void Construct(std::string)':
palindrome.cpp:107:61: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
107 | f[i][j] = min(f[i - 1][j], f[i - 1][j + (1 << i - 1)]);
| ~~^~~
palindrome.cpp: In function 'bool is_palindrome(int, int)':
palindrome.cpp:126:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
126 | int u = l + r >> 1;
| ~~^~~
palindrome.cpp: In function 'std::vector<std::pair<int, int> > Distinct_palindrome_substring(std::string)':
palindrome.cpp:140:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
140 | int mid = l + r >> 1;
| ~~^~~
palindrome.cpp:156:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
156 | int mid = l + r >> 1;
| ~~^~~
palindrome.cpp: In function 'int count_occurences(int, int, std::string&)':
palindrome.cpp:192:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
192 | int mid = L + R >> 1;
| ~~^~~
palindrome.cpp:199:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
199 | int mid = L + R >> 1;
| ~~^~~
# | 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... |