oj.uz

답안 #77005

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
77005 2018-09-20T04:18:52 Z samuelfgs96 회문 (APIO14_palindrome) C++11
8 / 100
 227 ms 132096 KB 
#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 {
//	int table[N*2][LN], n;
	int table[200][LN], n;
	rmq () { }
	rmq (int n) : n(n) {
		for (int i = 0; i < n; i++) {
			table[i][0] = L[i];
		}
		for (int j = 1; (1<<j) <= n; j++)
		for (int i = 0; i + (1<<j) <= n; i++)
			table[i][j] = max(table[i][j-1], table[i+(1<<(j-1))][j-1]);
	}
	int query (int l, int r) {
		int sz = r - l + 1;
		int lg = _log[sz];
		return max(table[l][lg], table[r - (1<<lg) + 1][lg]);
	}
} 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);
			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);
	dfs(0, 0);
	memset (pai, -1, sizeof pai);
	solve(0, 0);
	cout << ans << endl;
	return 0;
}

Compilation message

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.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 44408 KB Output is correct
2 Correct 40 ms 44664 KB Output is correct
3 Correct 39 ms 44732 KB Output is correct
4 Correct 40 ms 44732 KB Output is correct
5 Correct 39 ms 44732 KB Output is correct
6 Correct 39 ms 44788 KB Output is correct
7 Correct 40 ms 44808 KB Output is correct
8 Correct 39 ms 44812 KB Output is correct
9 Correct 41 ms 44844 KB Output is correct
10 Correct 40 ms 44844 KB Output is correct
11 Correct 90 ms 44872 KB Output is correct
12 Correct 39 ms 44972 KB Output is correct
13 Correct 41 ms 44972 KB Output is correct
14 Correct 39 ms 45056 KB Output is correct
15 Correct 40 ms 45056 KB Output is correct
16 Correct 40 ms 45056 KB Output is correct
17 Correct 42 ms 45056 KB Output is correct
18 Correct 41 ms 45056 KB Output is correct
19 Correct 40 ms 45056 KB Output is correct
20 Correct 39 ms 45056 KB Output is correct
21 Correct 39 ms 45056 KB Output is correct
22 Correct 52 ms 45056 KB Output is correct
23 Correct 39 ms 45056 KB Output is correct
24 Correct 39 ms 45056 KB Output is correct
25 Correct 39 ms 45056 KB Output is correct
26 Correct 39 ms 45056 KB Output is correct
27 Correct 40 ms 45056 KB Output is correct
28 Correct 40 ms 45056 KB Output is correct
29 Correct 39 ms 45056 KB Output is correct
30 Correct 40 ms 45056 KB Output is correct
31 Correct 43 ms 45056 KB Output is correct
32 Correct 43 ms 45056 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 85 ms 84576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 95 ms 86560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 136 ms 105716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 227 ms 132096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -