oj.uz

답안 #76873

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
76873 2018-09-18T21:37:39 Z samuelfgs96 회문 (APIO14_palindrome) C++11
47 / 100
 1000 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][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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 64120 KB Output is correct
2 Correct 55 ms 64132 KB Output is correct
3 Correct 56 ms 64304 KB Output is correct
4 Correct 56 ms 64304 KB Output is correct
5 Correct 56 ms 64488 KB Output is correct
6 Correct 55 ms 64488 KB Output is correct
7 Correct 55 ms 64488 KB Output is correct
8 Correct 54 ms 64488 KB Output is correct
9 Correct 54 ms 64488 KB Output is correct
10 Correct 58 ms 64488 KB Output is correct
11 Correct 54 ms 64488 KB Output is correct
12 Correct 54 ms 64488 KB Output is correct
13 Correct 55 ms 64488 KB Output is correct
14 Correct 57 ms 64488 KB Output is correct
15 Correct 55 ms 64488 KB Output is correct
16 Correct 55 ms 64488 KB Output is correct
17 Correct 55 ms 64488 KB Output is correct
18 Correct 55 ms 64492 KB Output is correct
19 Correct 58 ms 64496 KB Output is correct
20 Correct 57 ms 64496 KB Output is correct
21 Correct 56 ms 64496 KB Output is correct
22 Correct 58 ms 64552 KB Output is correct
23 Correct 62 ms 64552 KB Output is correct
24 Correct 55 ms 64552 KB Output is correct
25 Correct 56 ms 64564 KB Output is correct
26 Correct 57 ms 64564 KB Output is correct
27 Correct 56 ms 64564 KB Output is correct
28 Correct 55 ms 64564 KB Output is correct
29 Correct 57 ms 64564 KB Output is correct
30 Correct 58 ms 64564 KB Output is correct
31 Correct 55 ms 64564 KB Output is correct
32 Correct 55 ms 64564 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 64740 KB Output is correct
2 Correct 58 ms 64740 KB Output is correct
3 Correct 62 ms 64788 KB Output is correct
4 Correct 58 ms 64788 KB Output is correct
5 Correct 60 ms 64880 KB Output is correct
6 Correct 60 ms 64884 KB Output is correct
7 Correct 64 ms 64884 KB Output is correct
8 Correct 61 ms 64884 KB Output is correct
9 Correct 59 ms 64884 KB Output is correct
10 Correct 57 ms 64884 KB Output is correct
11 Correct 58 ms 64884 KB Output is correct
12 Correct 66 ms 64884 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 66320 KB Output is correct
2 Correct 94 ms 66332 KB Output is correct
3 Correct 136 ms 66836 KB Output is correct
4 Correct 129 ms 66836 KB Output is correct
5 Correct 63 ms 66836 KB Output is correct
6 Correct 66 ms 66836 KB Output is correct
7 Correct 80 ms 66836 KB Output is correct
8 Correct 65 ms 66836 KB Output is correct
9 Correct 63 ms 66836 KB Output is correct
10 Correct 65 ms 66836 KB Output is correct

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1080 ms 80744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

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