이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int N = 312345;
string s;
int at;
struct No {
int L, R, p, suff;
map <char, int> f;
No() {}
No(int l, int r, int P) : L(l), R(r), p(P) {}
inline int len () {
return R-L+1;
}
inline char operator[] (int i) {
return s[L + i];
}
void print() {
for (int i = 0; i < len(); i++) printf("%c", (*this)[i]);
}
} t[2*N];
int novo (int L, int R, int p) {
t[at] = No (L, R, p);
at++;
return at-1;
}
void build_suffix_tree () {
novo (0, -1, -1); //criando raiz
s += "$";
int i = 0, cn = 0, cd = 0, ns = 0;
int n = s.size();
for (int j = 0; j < s.size(); j++) {
for (; i <= j; i++) {
if (t[cn].len() == cd ? t[cn].f.count(s[j]) : t[cn][cd] == s[j]) {//CASO 1
if (t[cn].len() == cd) {
cd = 0;
cn = t[cn].f[s[j]];
}
cd++;
break;
} else if (t[cn].len() == cd) {//CASO 2
t[cn].f[s[j]] = novo(j, n-1, cn);
if (cn) {
cn = t[cn].suff;
cd = t[cn].len();
}
} else {//CASO 3 (precisa criar o suffix link)
//quebrar a aresta
int mid = novo (t[cn].L, t[cn].L + cd - 1, t[cn].p);
t[t[mid].p].f[t[mid][0]] = mid;
t[mid].f[s[j]] = novo (j, n-1, mid);
t[mid].f[t[cn][cd]] = cn;
t[cn].p = mid;
t[cn].L += cd;
if (ns) t[ns].suff = mid;
//achar o suffix link de mid
cn = t[mid].p;
int g;
if (cn) {
cn = t[cn].suff;
g = j - cd;
} else g = i+1;
while (g < j && g + t[t[cn].f[s[g]]].len() <= j) {
cn = t[cn].f[s[g]];
g += t[cn].len();
}
if (g == j) {
t[mid].suff = cn;
cd = t[cn].len();
ns = 0;
} else { // g < j
ns = mid;
cn = t[cn].f[s[g]];
cd = j - g;
}
}
}
}
}
int L[N*2]; //LPS Length Array
void findLongestPalindromicString() {
string text = s;
int N = text.size();
if(N == 0)
return;
N = 2*N + 1; //Position count
L[0] = 0;
L[1] = 1;
int C = 1; //centerPosition
int R = 2; //centerRightPosition
int i = 0; //currentRightPosition
int iMirror; //currentLeftPosition
int maxLPSLength = 0;
int maxLPSCenterPosition = 0;
int start = -1;
int end = -1;
int diff = -1;
//Uncomment it to print LPS Length array
//printf("%d %d ", L[0], L[1]);
for (i = 2; i < N; i++)
{
//get currentLeftPosition iMirror for currentRightPosition i
iMirror = 2*C-i;
L[i] = 0;
diff = R - i;
//If currentRightPosition i is within centerRightPosition R
if(diff > 0)
L[i] = min(L[iMirror], diff);
//Attempt to expand palindrome centered at currentRightPosition i
//Here for odd positions, we compare characters and
//if match then increment LPS Length by ONE
//If even position, we just increment LPS by ONE without
//any character comparison
while ( ((i + L[i]) < N && (i - L[i]) > 0) &&
( ((i + L[i] + 1) % 2 == 0) ||
(text[(i + L[i] + 1)/2] == text[(i - L[i] - 1)/2] )))
{
L[i]++;
}
if(L[i] > maxLPSLength) // Track maxLPSLength
{
maxLPSLength = L[i];
maxLPSCenterPosition = i;
}
//If palindrome centered at currentRightPosition i
//expand beyond centerRightPosition R,
//adjust centerPosition C based on expanded palindrome.
if (i + L[i] > R)
{
C = i;
R = i + L[i];
}
//Uncomment it to print LPS Length array
//printf("%d ", L[i]);
}
//printf("\n");
start = (maxLPSCenterPosition - maxLPSLength)/2;
end = start + maxLPSLength - 1;
}
int pos[N], pai[N*2], sz[N*2], ac[N*2], comeco[N];
void dfs (int u, int len) {
len += t[u].len();
if (t[u].R + 1 == (int)s.size()) {
pos[int(s.size()) - len] = u;
comeco[u] = int(s.size()) - len;
sz[u] = 1;
return ;
}
for (auto v : t[u].f) {
dfs(v.se, len);
sz[u] += sz[v.se];
comeco[u] = comeco[v.se];
}
}
const int LN = 20;
int _log[2*N+10];
struct rmq {
vector<int> t;
int n;
rmq () { }
rmq(int n):t(2*n, -0x3f3f3f3f), n(n) {}
void update(int p, int v) {
for (t[p+=n] = v; p > 1; p >>= 1) {
t[p>>1]=max(t[p], t[p^1]);
}
}
int query(int l, int r) {
int ans = -0x3f3f3f3f;
for (l += n, r += n; l < r; l >>= 1, r >>=1) {
if (l&1) ans = max(ans, t[l++]);
if (r&1) ans = max(ans, t[--r]);
}
return ans;
}
} st;
ll ans = 0;
void solve (int u, ll len) {
len += t[u].len();
if (len) {
int l = comeco[u];
int r = comeco[u] + len - 1;
//find longest palindrome in l r
l = l * 2;
r = r * 2 + 2;
int lo = 0, hi = r-l+1, ans = 0;
while (lo <= hi) {
int mid = (lo + hi) / 2;
int ql = l + mid, qr = r - mid;
if (ql > qr) {
hi = mid-1;
continue;
}
int ret = st.query(ql, qr+1);
if (ret >= mid) {
ans = mid;
lo = mid+1;
} else hi = mid-1;
}
::ans = max(::ans, sz[u] * ll(ans));
}
for (auto v : t[u].f)
solve(v.se, len);
}
int main (void) {
_log[1] = 0;
for (int i = 2; i < 2*N; i++) {
_log[i] = _log[i-1];
if ( (1<<(_log[i] + 1)) == i) _log[i]++;
}
cin >> s;
int n = s.size();
build_suffix_tree();
findLongestPalindromicString();
st = rmq(2*n+1);
for (int i = 0; i <= 2*n; i++) st.update(i, L[i]);
dfs(0, 0);
memset (pai, -1, sizeof pai);
solve(0, 0);
cout << ans << endl;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
palindrome.cpp: In function 'void build_suffix_tree()':
palindrome.cpp:36:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < s.size(); j++) {
~~^~~~~~~~~~
palindrome.cpp: In function 'void findLongestPalindromicString()':
palindrome.cpp:100:9: warning: variable 'end' set but not used [-Wunused-but-set-variable]
int end = -1;
^~~
palindrome.cpp: In function 'int novo(int, int, int)':
palindrome.cpp:10:8: warning: '<anonymous>.No::suff' is used uninitialized in this function [-Wuninitialized]
struct No {
^~
# | 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... |