Submission #103337

#	Time	Username	Problem	Language	Result	Execution time	Memory
103337		Minnakhmetov	Palindromes (APIO14_palindrome)	C++14	0 / 100	73 ms	34944 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, A = 26;
int to[N][A], link[N], len[N], w[N];
string s;
int n, z = 2, suf;

void addLetter(int p) {
	while (p - len[suf] - 1 < 0 || s[p - len[suf] - 1] != s[p])
		suf = link[suf];

	int c = s[p] - 'a';
	if (to[suf][c] != -1) {
		suf = to[suf][c];
		w[to[suf][c]]++;
		return;
	}

	
	to[suf][c] = z;
	w[z]++;
	len[z] = len[suf] + 2;

	if (len[z] == 1) {
		link[z] = 0;
	}
	else {
		int v = link[suf];
		while (p - len[v] - 1 < 0 || s[p - len[v] - 1] != s[p])
			v = link[v];

		link[z] = to[v][c];
	}

	suf = z;
	z++;
}

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;
	n = s.size();

	memset(to, -1, sizeof(to));

	len[0] = 0;
	len[1] = -1;
	link[0] = 1;
	link[1] = 1;

	suf = 0;

	for (int i = 0; i < n; i++) {
		addLetter(i);
	}

	for (int i = z - 1; i >= 0; i--) {
		w[link[i]] += w[i];
	}

	ll ans = 0;

	for (int i = 0; i < z; i++) {
		ans = max(ans, len[i] * (ll)w[i]);
	}

	cout << ans;

	return 0;
}

Compilation message (stderr)

palindrome.cpp:41:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable : 4996)

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