Submission #76873

#	Time	Username	Problem	Language	Result	Execution time	Memory
76873		samuelfgs96	Palindromes (APIO14_palindrome)	C++11	47 / 100	1080 ms	132096 KiB

palindrome

#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;
}

Compilation message (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 {
        ^~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27