제출 #76873

#제출 시각아이디문제언어결과실행 시간메모리
76873samuelfgs96회문 (APIO14_palindrome)C++11
47 / 100
1080 ms132096 KiB
#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][20], sz[N], ac[N]; 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...