Submission #288875

#	Time	Username	Problem	Language	Result	Execution time	Memory
288875		Namnamseo	Palindromes (APIO14_palindrome)	C++17	0 / 100	576 ms	49272 KiB

palindrome

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
using ll=long long;
#define pb push_back
#define rep(i,n) for(int i=0;i<n;++i)

const int maxn = int(6e5) + 10;

char s[300010];
int n;

int nxt[maxn][27];
int fn[maxn][27];
int fail[maxn];
int cnt[maxn], dep[maxn], par[maxn];
int myv[maxn];

int rad[maxn];
int here[maxn];
int nn, root;

int G(int v, int i) {
	if (!nxt[v][i]) {
		nxt[v][i] = ++nn;
		dep[nn] = dep[v] + 1;
		par[nn] = v;
	}
	return nxt[v][i];
}

int Q[maxn], head, tail;

int main() {
	scanf("%s", s);
	n = strlen(s);

	{ // inflate
		for (int i=n-1; 0<=i; --i) s[2*i+1] = s[i];
		for (int i=0; i<=n; ++i) s[2*i] = '{';
		n = 2*n+1;
	}

	// manacher
	for (int i=0, b=0; i<n; ++i) {
		int r=0;
		if (i<=b+rad[b]) r=min(b+rad[b]-i, rad[2*b-i]);
		while (i+r+1<n && i-r-1>=0 &&
			s[i+r+1] == s[i-r-1]) ++r;
		rad[i]=r;
		if (b+rad[b] < i+rad[i]) {
			for(int j=b+rad[b]+1; j<=i+rad[i]; ++j) here[j]=i;
			b=i;
		}
	}

	// ptree
	root = ++nn;
	for (int i=0; i<n; ++i) {
		int t = here[i];
		int len = i-t;
		int p;
		if (len == 0) p = root;
		else {
			int b = i-1, l = len-1;
			while (here[b] != b-l) b = 2*here[b] - (b-l) +l;
			p = myv[b];
		}
		myv[i] = G(p, s[i]-'a');
		par[myv[i]] = p;
	}

	rep(i, 27) {
		int v = nxt[root][i];
		if (v) { fn[root][i]=v; fail[v] = root; Q[head++] = v; }
		else fn[root][i] = root;
	}

	while (tail < head) {
		int v = Q[tail++];
		rep(i, 27) { int u = nxt[v][i];
			if (u) {
				fn[v][i]=u; fail[u]=fn[fail[v]][i]; Q[head++]=u;
			} else fn[v][i]=fn[fail[v]][i];
		}
	}

	rep(i, n) ++cnt[myv[i]];
	for(int i=tail-1; 0<=i; --i) cnt[fail[Q[i]]] += cnt[Q[i]];
	ll ans = 0;
	for(int i=1; i<=nn; ++i) ans = max(ans, (dep[i]-1)*1ll*cnt[i]);

	printf("%lld\n", ans);

	return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |  scanf("%s", s);
      |  ~~~~~^~~~~~~~~

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