제출 #554984

#제출 시각아이디문제언어결과실행 시간메모리
554984sidon회문 (APIO14_palindrome)C++17
100 / 100
39 ms33504 KiB
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;

const int Z = 3e5+2, B = 26;

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

int n, __s[Z] {-1}, *s = __s + 1;
string _s;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> _s;
	n = _s.size();
	for(int i = 0; i < n; ++i) {
		s[i] = _s[i] - 'a';
		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]);

			sz[cur] = sz[p] + 2;
			c[p][s[i]] = cur;
			v = sz[v] + 2 < sz[cur] ? c[v][s[i]] : 1;
			cur++;
		}
		++cnt[p = c[p][s[i]]];
	}

	i64 res {};

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

	cout << res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...