Submission #554992

#	Time	Username	Problem	Language	Result	Execution time	Memory
554992		sidon	회문 (APIO14_palindrome)	C++17	100 / 100	43 ms	32292 KiB

palindrome

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

const int Z = 3e5+2;

int n, sz[Z] {-1}, sLink[Z], cnt[Z], cur = 2, p = 1;
map<char, int> c[Z];
string s;

int main() {
	cin >> s; n = size(s);
	s = '_' + s;

	for(int i = 1; i <= n; ++i) {
		for(; s[i-sz[p]-1] != s[i]; p = sLink[p]);

		if(!c[p][s[i]]) {
			int &v = (sLink[cur] = sLink[p]);
			for(; s[i-sz[v]-1] != s[i]; v = sLink[v]);
			v = max(1, c[v][s[i]]);

			sz[cur] = sz[p] + 2;
			c[p][s[i]] = cur++;
		}
		++cnt[p = c[p][s[i]]];
	}

	long long res {};

	for(int u = cur; u--; ) {
		res = max(res, 1LL * cnt[u] * sz[u]);
		cnt[sLink[u]] += cnt[u];
	}

	cout << res;
}

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