Submission #106088

#	Time	Username	Problem	Language	Result	Execution time	Memory
106088		Saboon	Palindromes (APIO14_palindrome)	C++14	0 / 100	1078 ms	78388 KiB

palindrome

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int maxn = 3e5 + 10;
const int base = 37;
const int mod = 1e9 + 7;

int n;
string s;
int sa[maxn], pos[maxn], pw[maxn], hsh[maxn], rev[maxn], lmq[19][maxn], rmq[19][maxn];
ll answer;

vector<int> seg[4 * maxn];

int get_rev(int L, int R){
	ll ret = rev[L] - 1ll * rev[R + 1] * pw[R - L + 1] % mod;
	if (ret < 0)
		ret += mod;
	return ret;
}

int get_hsh(int L, int R){
	if (L == 0)
		return hsh[R];
	ll ret = hsh[R] - 1ll * hsh[L - 1] * pw[R - L + 1] % mod;
	if (ret < 0)
		ret += mod;
	return ret;
}

int lcp(int fi, int se){
	if (fi == se)
		return n - fi;
	fi = pos[fi], se = pos[se];
	if (fi > se)
		swap(fi, se);
	int len = se - fi;
	len = log2(len);
	return min(rmq[len][fi], lmq[len][se]);
}

int lcp_with_hash(int fi, int se){
	int lo = 0, hi = min(n - fi + 1, n - se + 1);
	while (hi - lo > 1){
		int mid = (lo + hi) >> 1;
		if (get_hsh(fi, fi + mid - 1) == get_hsh(se, se + mid - 1))
			lo = mid;
		else
			hi = mid;
	}
	return lo;
}

bool cmp(int fi, int se){
	int lo = 0, hi = min(n - fi + 1, n - se + 1);
	while (hi - lo > 1){
		int mid = (lo + hi) >> 1;
		if (get_hsh(fi, fi + mid - 1) == get_hsh(se, se + mid - 1))
			lo = mid;
		else
			hi = mid;
	}
	if (lo == n - fi or (lo < n - se and s[fi + lo] < s[se + lo]))
		return 1;
	return 0;
}

void buildSA(){
	for (int i = 0; i < n; i++)
		sa[i] = i;
	sort(sa, sa + n, cmp);
	for (int i = 0; i < n; i++)
		pos[sa[i]] = i;
	memset(rmq, 63, sizeof rmq);
	memset(lmq, 63, sizeof lmq);
	for (int i = 0; i < n - 1; i++){
		int tmp = lcp_with_hash(sa[i], sa[i + 1]);
		rmq[0][i] = tmp;
		lmq[0][i + 1] = tmp;
	}
	for (int i = 0; i < 18; i++)
		for (int j = 0; j + (1 << i) < n; j++)
			rmq[i + 1][j] = min(rmq[i][j], rmq[i][j + (1 << i)]);
	for (int i = 0; i < 18; i++)
		for (int j = n - 1; j - (1 << i) >= 0; j--)
			lmq[i + 1][j] = min(lmq[i][j], lmq[i][j - (1 << i)]);

}

void check(int L, int R){
	int len = R - L + 1;
	int fi, se;
	int lo = -1, hi = pos[L];
	while (hi - lo > 1){
		int mid = (lo + hi) >> 1;
		if (lcp(L, sa[mid]) >= len)
			hi = mid;
		else
			lo = mid;
	}
	fi = hi;
	lo = pos[L], hi = n;
	while (hi - lo > 1){
		int mid = (lo + hi) >> 1;
		if (lcp(L, sa[mid]) >= len)
			lo = mid;
		else
			hi = mid;
	}
	se = lo;
	answer = max(answer, 1ll * len * (se - fi + 1));
}

void get(int id, int L, int R, int idx, int len){
	for (int i = 0; i < seg[id].size() and seg[id][i] < 0; i++){
		int t = -seg[id][i];
		t --;
		t = (t - idx + 1);
		if (2 * t <= len)
			break;
		check(idx, idx + 2 * t - 1);
	}
	for (int i = (int)(seg[id].size()) - 1; i >= 0 and seg[id][i] > 0; i--){
		int t = seg[id][i];
		t --;
		t = (t - idx);
		if (2 * t + 1 <= len)
			break;
		check(idx, idx + 2 * t);
	}
	if (L + 1 == R)
		return;
	int mid = (L + R) >> 1;
	if (idx < mid)
		get(2 * id + 0, L, mid, idx, len);
	else
		get(2 * id + 1, mid, R, idx, len);
}

void add(int id, int L, int R, int l, int r, int x){
	if (L == l and R == r){
		seg[id].push_back(x);
		return;
	}
	int mid = (L + R) >> 1;
	if (l < mid)
		add(2 * id + 0, L, mid, l, min(mid, r), x);
	if (mid < r)
		add(2 * id + 1, mid, R, max(l, mid), r, x);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin >> s;
	n = s.size();
	pw[0] = 1;
	for (int i = 1; i <= n; i++)
		pw[i] = pw[i - 1] * base % mod;
	for (int i = 0; i < n; i++){
		if (i == 0)
			hsh[i] = (int)(s[i] - 'a' + 1);
		else
			hsh[i] = (hsh[i - 1] * base + (int)(s[i] - 'a' + 1)) % mod;
	}
	for (int i = n - 1; i >= 0; i--)
		rev[i] = (rev[i + 1] * base + (int)(s[i] - 'a' + 1)) % mod;
	buildSA();
	for (int i = 0; i < n; i++){
		int lo = 0, hi = min(i, n - i - 1) + 1;
		while (hi - lo > 1){
			int mid = (lo + hi) >> 1;
			if (get_hsh(i - mid, i - 1) == get_rev(i + 1, i + mid))
				lo = mid;
			else
				hi = mid;
		}
		add(1, 0, n, i - lo, i + 1, i + 1);
		if (i < n - 1){
			lo = 0, hi = min(i + 2, n - i);
			while (hi - lo > 1){
				int mid = (lo + hi) >> 1;
				if (get_hsh(i - mid + 1, i) == get_rev(i + 1, i + mid))
					lo = mid;
				else
					hi = mid;
			}
			if (lo > 0)
				add(1, 0, n, i - lo + 1, i + 1, -(i+1));
		}
	}
	for (int i = 1; i < 4 * maxn; i++)
		sort(seg[i].begin(), seg[i].end());
	for (int i = 0; i < n; i++){
		int idx = sa[i];
		int len = 0;
		if (i > 0)
			len = lcp(sa[i], sa[i - 1]);
		get(1, 0, n, idx, len);
	}
	cout << answer << endl;
}

Compilation message (stderr)

palindrome.cpp: In function 'void get(int, int, int, int, int)':
palindrome.cpp:118:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < seg[id].size() and seg[id][i] < 0; i++){
                  ~~^~~~~~~~~~~~~~~~

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