이 제출은 이전 버전의 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][20], sz[N*2], ac[N*2];
ll f (int l, int r) {
int u = pos[l];
int len = r - l + 1;
//preciso subir até o primeiro vertice em que ac[x] >= sz
for (int i = 19; i >= 0; i--) {
if (pai[u][i] == -1) continue;
int v = pai[u][i];
if (ac[v] >= len) u = v;
}
return sz[u] * ll(len);
/*
string xt = s.substr(l, sz);
ll ct = 0;
for (int i = 0; i < s.size(); i++) {
int j = i + sz;
if (j > s.size()) continue;
string bt = s.substr(i, sz);
if (bt == xt) ct++;
}
return ct * sz; */
}
void dfs (int u, int len) {
len += t[u].len();
sz[u] = 0;
ac[u] = len;
if (t[u].R + 1 == (int)s.size()) {
pos[int(s.size()) - len] = u;
sz[u] = 1;
return ;
}
for (auto v : t[u].f) {
pai[v.se][0] = u;
dfs(v.se, len);
sz[u] += sz[v.se];
}
}
int main (void) {
cin >> s;
int n = s.size();
build_suffix_tree();
findLongestPalindromicString();
memset (pai, -1, sizeof pai);
dfs(0, 0);
for (int j = 1; j < 20; j++)
for (int i = 0; i < at; i++)
if (pai[i][j-1] != -1)
pai[i][j] = pai[pai[i][j-1]][j-1];
ll ans = 0;
//testar só os impares
for (int i = 0; i < n; i++) {
int id = i * 2 + 1;
int lo = 0, hi = L[id]/2;
while (hi - lo >= 6) {
int m1 = lo + (hi - lo) / 3;
int m2 = hi - (hi - lo) / 3;
if (f(i-m1, i+m1) > f(i-m2, i+m2))
hi = m2;
else
lo = m1;
}
for (int x = lo; x <= hi; x++)
ans = max(ans, f(i-x, i+x));
}
//testar só os pares
for (int i = 0; i < n; i++) {
int id = i * 2 + 2;
if (!L[id]) continue;
int lo = 0, hi = L[id]/2;
int sz = 2;
int st = i;
while (hi - lo >= 6) {
int m1 = lo + (hi - lo) / 3;
int m2 = hi - (hi - lo) / 3;
if (f(i-m1+1, i+m1) > f(i-m2+1, i+m2))
hi = m2;
else
lo = m1;
}
for (int x = lo; x <= hi; x++)
ans = max(ans, f(i-x+1, i+x));
}
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 main()':
palindrome.cpp:220:7: warning: unused variable 'sz' [-Wunused-variable]
int sz = 2;
^~
palindrome.cpp:221:7: warning: unused variable 'st' [-Wunused-variable]
int st = i;
^~
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... |