oj.uz

답안 #76874

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
76874 2018-09-18T21:41:36 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*2][20], sz[N*2], ac[N*2];
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 78 ms 88568 KB Output is correct
2 Correct 73 ms 88612 KB Output is correct
3 Correct 75 ms 88724 KB Output is correct
4 Correct 74 ms 88844 KB Output is correct
5 Correct 74 ms 88844 KB Output is correct
6 Correct 75 ms 88844 KB Output is correct
7 Correct 76 ms 88844 KB Output is correct
8 Correct 73 ms 88916 KB Output is correct
9 Correct 76 ms 88916 KB Output is correct
10 Correct 75 ms 88916 KB Output is correct
11 Correct 73 ms 88916 KB Output is correct
12 Correct 76 ms 88916 KB Output is correct
13 Correct 93 ms 88916 KB Output is correct
14 Correct 74 ms 88916 KB Output is correct
15 Correct 73 ms 88916 KB Output is correct
16 Correct 72 ms 88916 KB Output is correct
17 Correct 85 ms 88948 KB Output is correct
18 Correct 73 ms 88948 KB Output is correct
19 Correct 74 ms 88948 KB Output is correct
20 Correct 76 ms 88952 KB Output is correct
21 Correct 73 ms 88952 KB Output is correct
22 Correct 74 ms 88952 KB Output is correct
23 Correct 74 ms 89008 KB Output is correct
24 Correct 76 ms 89132 KB Output is correct
25 Correct 76 ms 89132 KB Output is correct
26 Correct 74 ms 89132 KB Output is correct
27 Correct 75 ms 89132 KB Output is correct
28 Correct 87 ms 89132 KB Output is correct
29 Correct 74 ms 89132 KB Output is correct
30 Correct 74 ms 89132 KB Output is correct
31 Correct 75 ms 89132 KB Output is correct
32 Correct 75 ms 89132 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 89316 KB Output is correct
2 Correct 77 ms 89316 KB Output is correct
3 Correct 78 ms 89320 KB Output is correct
4 Correct 77 ms 89320 KB Output is correct
5 Correct 77 ms 89332 KB Output is correct
6 Correct 78 ms 89456 KB Output is correct
7 Correct 75 ms 89456 KB Output is correct
8 Correct 77 ms 89456 KB Output is correct
9 Correct 76 ms 89456 KB Output is correct
10 Correct 74 ms 89456 KB Output is correct
11 Correct 76 ms 89456 KB Output is correct
12 Correct 76 ms 89456 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 90640 KB Output is correct
2 Correct 108 ms 90652 KB Output is correct
3 Correct 159 ms 91064 KB Output is correct
4 Correct 149 ms 91064 KB Output is correct
5 Correct 83 ms 91064 KB Output is correct
6 Correct 88 ms 91064 KB Output is correct
7 Correct 103 ms 91064 KB Output is correct
8 Correct 84 ms 91064 KB Output is correct
9 Correct 84 ms 91064 KB Output is correct
10 Correct 84 ms 91064 KB Output is correct

Subtask #4
0 / 26.0

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

Subtask #5
0 / 27.0

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