Submission #103291

#	Time	Username	Problem	Language	Result	Execution time	Memory
103291		Minnakhmetov	Palindromes (APIO14_palindrome)	C++14	73 / 100	1076 ms	128180 KiB

palindrome

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
#pragma warning(disable : 4996)

const int N = 3e5 + 5, L = 20, X[2] = { 997, 883 }, M[2] = { (int)1e9 + 7, (int)1e9 + 9 };
int suf[L][N], cl[L][N], ct[N], pos[N], lcp[N], lb[N], rb[N];
ll h[2][N], rh[2][N], p[2][N];
int n;
string s;


bool isPalindrome(int l, int r) {
	for (int i = 0; i < 2; i++) {
		ll h1 = (h[i][r + 1] - h[i][l] * p[i][r - l + 1] % M[i] + M[i]) % M[i],
			h2 = (rh[i][n - l] - rh[i][n - r - 1] * p[i][r - l + 1] % M[i] + M[i]) % M[i];
		if (h1 != h2)
			return false;
	}
	return true;
}



//bool isPalindrome2(string s) {
//	for (int i = 0; i < s.size() / 2; i++) {
//		if (s[i] != *(s.end() - 1 - i))
//			return false;
//	}
//	return true;
//}
//
//ll brute() {
//	ll ans = 0;
//	map<string, int> mp;
//	for (int i = 0; i < n; i++) {
//		for (int j = i; j < n; j++) {
//			mp[s.substr(i, j - i + 1)]++;
//		}
//	}
//	for (auto &p : mp) {
//		if (isPalindrome2(p.first))
//			ans = max(ans, p.first.size() * (ll)p.second);
//	}
//	return ans;
//}

signed main() {
#ifdef HOME
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> s;

	s.push_back('#');

	n = s.size();

	for (int i = 0; i < n; i++) {
		ct[s[i]]++;
		cl[0][i] = s[i];
	}

	for (int i = 1; i < N; i++)
		ct[i] += ct[i - 1];

	for (int i = n - 1; i >= 0; i--) {
		suf[0][--ct[s[i]]] = i;
	}


	for (int i = 1; i < L; i++) {
		fill(ct, ct + N, 0);
		for (int j = 0; j < n; j++) {
			suf[i - 1][j] -= (1 << (i - 1)) % n;
			if (suf[i - 1][j] < 0)
				suf[i - 1][j] += n;
			ct[cl[i - 1][suf[i - 1][j]]]++;
		}

		for (int i = 1; i < N; i++) {
			ct[i] += ct[i - 1];
		}

		for (int j = n - 1; j >= 0; j--) {
			suf[i][--ct[cl[i - 1][suf[i - 1][j]]]] = suf[i - 1][j];
		}
		for (int j = 0, k = 0; j < n; j++) {
			cl[i][suf[i][j]] = k;
			if (cl[i - 1][suf[i][j]] != cl[i - 1][suf[i][j + 1]] ||
				cl[i - 1][(suf[i][j] + (1 << (i - 1))) % n] !=
				cl[i - 1][(suf[i][j + 1] + (1 << (i - 1))) % n])
				k++;
		}
	}

	for (int i = 0; i < n; i++) {
		pos[suf[L - 1][i]] = i;
	}

	for (int i = 0, k = 0; i < n; i++) {
		int j = pos[i];
		if (j == n - 1) {
			k = 0;
			continue;
		}
		j = suf[L - 1][j + 1];
		while (i + k < n && j + k < n && s[i + k] == s[j + k])
			k++;
		lcp[pos[i]] = k;
		k = max(0, k - 1);
	}


	n--;

	for (int j = 0; j < 2; j++) {
		p[j][0] = 1;
		for (int i = 0; i < n; i++) {
			p[j][i + 1] = p[j][i] * X[j] % M[j];
			h[j][i + 1] = (h[j][i] * X[j] + s[i]) % M[j];
			rh[j][i + 1] = (rh[j][i] * X[j] + s[n - 1 - i]) % M[j];
		}
	}
	vector<vector<int>> ev;

	ll ans = 0;

	for (int i = 0; i < n; i++) {
		int l = 0, r = min(i + 1, n - i);
		while (r - l > 1) {
			int p = (l + r) >> 1;
			if (isPalindrome(i - p, i + p))
				l = p;
			else
				r = p;
		}
		ans = max(ans, l * 2 + 1ll);
		ev.push_back({ i - l, i, 0 });

		if (s[i] == s[i + 1]) {
			l = 0, r = min(i + 1, n - i - 1);
			while (r - l > 1) {
				int p = (l + r) >> 1;
				if (isPalindrome(i - p, i + p + 1))
					l = p;
				else
					r = p;
			}
			ans = max(ans, l * 2 + 2ll);
			ev.push_back({ i - l, i, 1 });
		}
	}

	sort(all(ev));

	vector<int> v;
	for (int i = 1; i <= n; i++) {
		while (!v.empty() && lcp[v.back()] >= lcp[i])
			v.pop_back();
		lb[i] = v.empty() ? 1 : v.back() + 1;
		v.push_back(i);
	}
	v.clear();

	for (int i = n; i > 0; i--) {
		while (!v.empty() && lcp[v.back()] >= lcp[i])
			v.pop_back();
		rb[i] = v.empty() ? n - 1 : v.back();
		v.push_back(i);
	}

	set<int> st[2];
	for (int i = 0, j = 0; i < n; i++) {
		while (j < ev.size() && ev[j][0] == i) {
			st[ev[j][2]].insert(ev[j][1]);
			j++;
		}
		int k = pos[i], r = i + lcp[k] - 1;
		if (lcp[k] > 0) {
			
			auto it = st[0].upper_bound((r - i) / 2 + i);
			if (it != st[0].begin()) {
				it--;
				ll len = (*it - i) * 2 + 1;
				ans = max(ans, (rb[k] - lb[k] + 1) * len);
			}
		}
		if (lcp[k] > 1) {
			auto it = st[1].upper_bound((r - i - 1) / 2 + i);
			if (it != st[1].begin()) {
				it--;
				ll len = (*it - i) * 2 + 2;
				ans = max(ans, (rb[k] - lb[k] + 1) * len);
			}
		}
	}

	cout << ans;


	//cout << "\n" << brute();

	return 0;
}

Compilation message (stderr)

palindrome.cpp:41:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable : 4996)
 
palindrome.cpp: In function 'int main()':
palindrome.cpp:100:10: warning: array subscript has type 'char' [-Wchar-subscripts]
   ct[s[i]]++;
          ^
palindrome.cpp:108:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   suf[0][--ct[s[i]]] = i;
                   ^
palindrome.cpp:215:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (j < ev.size() && ev[j][0] == i) {
          ~~^~~~~~~~~~~

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