Submission #32153

#	Time	Username	Problem	Language	Result	Execution time	Memory
32153		minimario	Palindromes (APIO14_palindrome)	C++14	0 / 100	29 ms	53184 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;

const int MAX = 300005;

struct node {
	int len;
	int next[26];
	int suff;
	int ct;
};

node t[MAX];
int i = 0;
int ans = 0;

void roots() {
	t[0].len = -1; t[0].suff = 0;
	t[1].len = 0; t[1].suff = 0;
}

int ct = 2;
int maxsuff = 1;
string s;
void add(int pos) {
	int j = maxsuff;
	int c = s[pos] - 'a'; // the character
	while (s[pos-t[j].len-1] != s[pos]) {
		j = t[j].suff;
	}
	if (t[j].next[c] == 0) {
		t[j].next[c] = ct;
		t[ct].len = t[j].len + 2;
		ct++;
	}
	maxsuff = t[j].next[c];
	if (j == 0) {
		t[maxsuff].suff = 1;
	}
	else {
		j = t[j].suff;
		while (s[pos-t[j].len-1] != s[pos]) {
			j = t[j].suff; 
		}
		if (t[j].next[c] == 0) {
			t[j].next[c] = ct;
			t[ct].len = t[j].len + 2;
			ct++;
		}
		t[maxsuff].suff = t[j].next[c];
	}
	t[maxsuff].ct++;
}

bool v[MAX];

vector<int> g[MAX];
void create() {
	for (int i=2; i<=MAX; i++) {
		if (t[i].suff > 1) {
			g[t[i].suff].push_back(i);
		}
	}
}
void dfs(int u) {
	v[u] = true;
	for (int i : g[u]) {
		dfs(i);
		t[u].ct += t[i].ct;
	}
}

int main() {
	//freopen("a.in", "r", stdin);
	//freopen("a.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> s;
	s = " " + s;
	roots();
	for (int i=1; i<s.length(); i++) {
		add(i);
	}
	v[0] = v[1] = true;
	create();
	for (int i=2; i<=MAX; i++) {
		if (!v[i]) { dfs(i); }
	}
	long long maxi = 0;
	for (int i=2; i<MAX; i++) {
		maxi = max(maxi, (long long)t[i].len * (long long)t[i].ct);
	}
	cout << maxi << endl;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:81:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<s.length(); i++) {
                 ^
palindrome.cpp:87:11: warning: iteration 300003u invokes undefined behavior [-Waggressive-loop-optimizations]
   if (!v[i]) { dfs(i); }
           ^
palindrome.cpp:86:17: note: containing loop
  for (int i=2; i<=MAX; i++) {
                 ^

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