Submission #603247

#	Time	Username	Problem	Language	Result	Execution time	Memory
603247		thiago_bastos	Palindromes (APIO14_palindrome)	C++17	0 / 100	502 ms	31436 KiB

palindrome

#include "bits/stdc++.h"

using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;

struct SA {
	static vector<int> sa, ord, lcp, table;
	static vector<vector<int>> sp;
	static int mod_sum(int x, int n) {
		return x >= n ? x - n : x;
	}
	static void suffix_array(string& s) {
		s += "$";
		int n = s.size();
		vector<int> tmpSA(n), tmpOrd(n), cnt(max(128, n), 0);
		sa.resize(n);
		ord.resize(n);
		for(char ch : s) ++cnt[ch];
		for(int i = 1; i < 128; ++i) cnt[i] += cnt[i - 1];
		for(int i = 0; i < n; ++i) sa[--cnt[s[i]]] = i;
		ord[sa[0]] = 0;
		for(int i = 1; i < n; ++i) {
			int pre = sa[i - 1], cur = sa[i];
			ord[cur] = ord[pre] + (s[cur] != s[pre]);
		}
		int m = ord[sa[n - 1]] + 1;
		for(int l = 0; (1 << l) < n; ++l) {
			fill(cnt.begin(), cnt.begin() + m, 0);
			for(int i = 0; i < n; ++i) ++cnt[ord[i]];
			for(int i = 1; i < m; ++i) cnt[i] += cnt[i - 1];
			for(int i = n - 1; i >= 0; --i) {
				int j = mod_sum(sa[i] - (1 << l) + n, n);
				tmpSA[--cnt[ord[j]]] = j;
			}
			tmpOrd[tmpSA[0]] = 0;
			for(int i = 1; i < n; ++i) {
				int pre = tmpSA[i - 1], cur = tmpSA[i];
				auto x = make_pair(ord[pre], ord[mod_sum(pre + (1 << l), n)]);
				auto y = make_pair(ord[cur], ord[mod_sum(cur + (1 << l), n)]);
				tmpOrd[cur] = tmpOrd[pre] + (x != y);
			}
			swap(sa, tmpSA);
			swap(ord, tmpOrd);
			m = ord[sa[n - 1]] + 1;
		}
		s.pop_back();
		sa.erase(sa.begin());
	}
	static void buildLCP(string& s) {
		int n = s.size(), match = 0;
		suffix_array(s);
		table.resize(n);
		lcp.resize(n);
		for(int i = 0; i < n; ++i) table[sa[i]] = i;
		for(int i = 0; i < n; ++i) {
			if(table[i]) {
				int k = i + match, j = sa[table[i] - 1] + match;
				while(k < n && j < n && s[k] == s[j]) ++k, ++j;
				match = k - i;
			}
			lcp[table[i]] = match;
			match = max(0, match - 1);
		}
		int lg = 32 - __builtin_clz(n);
		sp = vector<vector<int>>(lg, vector<int>(n));
		for(int i = 0; i < n; ++i) sp[0][i] = lcp[i];
		for(int i = 1; i < lg; ++i)
		for(int j = 0; j + (1 << i) <= n; ++j)
			sp[i][j] = min(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
	}
	static int LCP(int i, int j) {
		int k = (int)sa.size() - i;
		i = table[i], j = table[j];
		if(i > j) swap(i, j);
		if(++i > j) return k;
		k = 31 - __builtin_clz(j - i + 1);
		return min(sp[k][i], sp[k][j - (1 << k) + 1]);
	}
	static int count(int l, int r) {
		int L = table[l], R = table[l], n = sa.size();
		for(int i = 31 - __builtin_clz(n); i >= 0; --i) {
			int _L = L - (1 << i), _R = R + (1 << i);
			if(_L >= 0 && LCP(sa[_L], l) >= r - l + 1) L = _L;
			if(_R < n && LCP(sa[_R], l) >= r - l + 1) R = _R;
		}
		return R - L + 1;
	}
};

vector<int> SA :: sa;
vector<int> SA :: ord;
vector<int> SA :: lcp;
vector<int> SA :: table;
vector<vector<int>> SA :: sp;

void manacher(string& s, vector<int>& d1, vector<int>& d2) {
	int l = 0, r = -1, n = s.size();
	d1.assign(n, 1);
	d2.assign(n, 0);
	for(int i = 0; i < n; ++i) {
		if(i <= r) {
			d1[i] = min(d1[l + r - i], r - i + 1);
			d2[i] = min(d2[l + r - i + 1], r - i + 1);
		}
		while(i + d1[i] < n && i - d1[i] >= 0 && s[i - d1[i]] == s[i + d1[i]]) ++d1[i];
		while(i + d2[i] < n && i - d2[i] - 1 >= 0 && s[i - d2[i] - 1] == s[i + d2[i]]) ++d2[i];
		if(r < i + d2[i] - 1) l = i - d2[i], r = i + d2[i] - 1;
		if(r < i + d1[i] - 1) l = i - d1[i] + 1, r = i + d1[i] - 1;
	}
}

void solve() {
	string s;
	i64 ans = 0;
	cin >> s;
	int n = s.size();	
	vector<int> d1, d2;
	manacher(s, d1, d2);
	SA :: buildLCP(s);
	int lg = 31 - __builtin_clz(n);
	for(int i = 0; i < n; ++i) {
		int m = 0;
		for(int j = lg; j >= 0; --j) {
			int _m = m + (1 << j);
			int l = i - _m;
			if(_m > d1[i]) continue;
			int x = SA :: table[l];
			if(!x) continue;
			int y = SA :: sa[x - 1];
			if(SA :: LCP(y, l) >= 2 * _m - 1) m = _m; 
		}
		for(; m <= d1[i]; ++m)
			ans = max(ans, (2ll * m - 1) * SA :: count(i - m, i + m));
	}
	for(int i = 0; i < n; ++i) {
		if(!d2[i]) continue;
		int m = 1;
		for(int j = lg; j >= 0; --j) {
			int _m = m + (1 << j);
			int l = i - _m;
			if(_m > d1[i]) continue;
			int x = SA :: table[l];
			if(!x) continue;
			int y = SA :: sa[x - 1];
			if(SA :: LCP(y, l) >= 2 * _m) m = _m; 
		}
		for(; m <= d2[i]; ++m)
			ans = max(ans, 2ll * m * SA :: count(i - m, i + m - 1));
	}
	cout << ans << '\n';
}

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

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