Submission #41654

#	Time	Username	Problem	Language	Result	Execution time	Memory
41654		kingpig9	Palindromes (APIO14_palindrome)	C++11	100 / 100	98 ms	63624 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 300763;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

struct palindromic_tree {
	int slen;	//total length of string
	char str[MAXN];
	int len[MAXN];
	int nnodes;
	int link[MAXN], nxt[MAXN][26];
	int last;
	int cnt[MAXN];	//count of the node
	vector<int> adj[MAXN];

	palindromic_tree() {
		str[0] = -1;
		slen = 1;
		link[0] = 1;
		len[1] = -1;
		nnodes = 2;
	}

	int getlink (int x) {
		while (str[slen - 2 - len[x]] != str[slen - 1]) {
			//debug("str[%d] != str[%d]\n", slen - 2 - len[x], slen - 1);
			x = link[x];
		}
		//debug("finally! str[%d] == str[%d]\n", slen - 2 - len[x], slen - 1);
		return x;
	}

	void add (char ch) {
		ch -= 'a';
		str[slen++] = ch;
		last = getlink(last);
		if (!nxt[last][ch]) {
			len[nnodes] = len[last] + 2;
			link[nnodes] = nxt[getlink(link[last])][ch];	//link with next char added to end
			nxt[last][ch] = nnodes;
			nnodes++;
		}
		last = nxt[last][ch];
	}

	void compute() {
		for (int i = 2; i < nnodes; i++) {
			adj[link[i]].push_back(i);
		}
	}

	void dfs (int x) {
		for (int y : adj[x]) {
			if (y) {
				dfs(y);
				cnt[x] += cnt[y];
			}
		}
	}
} tr;

int N;
char S[MAXN];

int main() {
	scanf("%s", S);
	N = strlen(S);
	for (int i = 0; i < N; i++) {
		tr.add(S[i]);
		tr.cnt[tr.last]++;
	}

	tr.compute();
	tr.dfs(0);
	tr.dfs(1);

	ll ans = 0;
	for (int i = 2; i < tr.nnodes; i++) {
		ans = max(ans, ll(tr.len[i]) * tr.cnt[i]);
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

palindrome.cpp: In member function 'void palindromic_tree::add(char)':
palindrome.cpp:45:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   if (!nxt[last][ch]) {
                    ^
palindrome.cpp:47:46: warning: array subscript has type 'char' [-Wchar-subscripts]
    link[nnodes] = nxt[getlink(link[last])][ch]; //link with next char added to end
                                              ^
palindrome.cpp:48:16: warning: array subscript has type 'char' [-Wchar-subscripts]
    nxt[last][ch] = nnodes;
                ^
palindrome.cpp:51:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   last = nxt[last][ch];
                      ^
palindrome.cpp: In function 'int main()':
palindrome.cpp:74:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", S);
                ^

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