Submission #77010

#	Time	Username	Problem	Language	Result	Execution time	Memory
77010		samuelfgs96	Palindromes (APIO14_palindrome)	C++11	73 / 100	1078 ms	112056 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*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;
}
 

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 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: 26 / 26
• Subtask 5: 0 / 27