萌新求助卡常 在时限边缘
查看原帖
萌新求助卡常 在时限边缘
852144
Loser_Syx楼主2025/1/9 22:35
#include <iostream>
#include <cassert>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <random>
#include <ctime>
#include <map>
#include <set>
using namespace std;
// #define int long long
#define pii pair<int, int>
#define eb emplace_back
#define F first
#define S second
#define test(x) cout << "Test: " << (x) << '\n'
#define lowbit(x) (x & -x)
#define debug puts("qwq");
#define open(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define close fclose(stdin);fclose(stdout);
namespace FastIO {
	template <typename T = int>
	inline T read() {
		T s = 0, w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		return s * w;
	}
	template <typename T>
	inline void read(T &s) {
		s = 0;
		int w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		s = s * w;
	}
	template <typename T, typename... Arp> inline void read(T &x, Arp &...arp) {
		read(x), read(arp...);
	}
	template <typename T>
	inline void write(T x, char ch = '\n') {
		if (x < 0) x = -x, putchar('-');
		static char stk[25];
		int top = 0;
		do {
			stk[top++] = x % 10 + '0', x /= 10;
		} while (x);
		while (top) putchar(stk[--top]);
		putchar(ch);
		return;
	}
	template <typename T>
	inline void smax(T &x, T y) {
		if (x < y) x = y;
	}
	template <typename T>
	inline void smin(T &x, T y) {
		if (x > y) x = y;
	}
	void quit() {
		exit(0);
	}
} using namespace FastIO;
const int N = 3e5 + 19, L = 21;
char s[N], c[N + N];
int tmp[N], sa[N], rnk[N], cnt[N], n, h[N], d[N], st[N][L], lg[N]; long long ans;
void SA() {
	for (int i = 0; i < n; ++i) sa[i] = i;
	sort(sa, sa + n, [&](int x, int y) { return s[x] < s[y]; } );
	for (int i = 0; i < n; ++i) {
		if (i && s[sa[i]] == s[sa[i-1]]) rnk[sa[i]] = rnk[sa[i-1]];
		else rnk[sa[i]] = i;
	}
	for (int w = 1; w < n; ++w) {
		for (int i = 0; i < w; ++i) tmp[i] = i + n - w;
		for (int i = 0, j = w; i < n; ++i) if (sa[i] >= w) tmp[j++] = sa[i] - w;
		for (int i = 0; i < n; ++i) cnt[i] = 0;
		for (int i = 0; i < n; ++i) ++cnt[rnk[i]];
		for (int i = 1; i < n; ++i) cnt[i] += cnt[i-1];
		for (int i = n-1; ~i; --i) sa[--cnt[rnk[tmp[i]]]] = tmp[i];
		bool ok=1;
		for (int i = 0; i < n; ++i) {
			if (i && rnk[sa[i]] == rnk[sa[i-1]] && (sa[i-1] + w >= n ? -1 : rnk[sa[i-1]+w]) == (sa[i] + w >= n ? -1 : rnk[sa[i]+w])) {
				tmp[sa[i]] = tmp[sa[i-1]]; ok = 0;
			}
			else tmp[sa[i]] = i;
		} for (int i = 0; i < n; ++i) rnk[i] = tmp[i];
		if (ok) break;
	}
	for (int i = 0, k = 0; i < n; ++i) {
		if (!rnk[i]) continue;
		if (k) --k;
		while (s[i+k] == s[sa[rnk[i]-1]+k]) ++k;
		h[rnk[i]] = k;
	}
} int query(int l, int r) {
	int t = lg[r - l + 1];
	return min(st[l][t], st[r - (1 << t) + 1][t]);
} void check(int L, int R) {
	int now = rnk[L], A, B, len = R - L + 1;
	int l = 1, r = now+1;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (query(mid, now) >= len) r = mid;
		else l = mid + 1;
	} A = r-1;
	l = now+1; r = n;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (query(now+1, mid) >= len) l = mid + 1;
		else r = mid;
	} B = r-1;
	smax(ans, 1LL * len * (B - A + 1));
} void Manacher() {
	int len = n * 2 + 1;
	c[0] = c[1] = '$'; for (int i = 0; i < n; ++i) c[i * 2 + 2] = s[i], c[i * 2 + 3] = '$';
	for (int l = 1, r = 0, p = 0; l < len; ++l) {
		if (l <= r) d[l] = min(d[p * 2 - l], r - l + 1);
		while (c[l - d[l]] == c[l + d[l]]) {
			if (d[l] + l > r && c[l - d[l]] == c[l + d[l]] && c[l - d[l]] == '$') {
				int mid = l / 2; int L = mid - ((d[l]-1) / 2), R = L + d[l] - 1;
				check(L-1, R-1);
			} ++d[l];
		}
		if (d[l] + l > r) r = d[l] + l - 1, p = l;
	}
} void ST() {
	for (int i = 2; i < N; ++i) { lg[i] = lg[i >> 1] + 1; }
	for (int i = 1; i < n; ++i) st[i][0] = h[i];
	for (int i = 1; i <= lg[n-1]; ++i) {
		for (int j = 1; j + (1 << i) - 1 < n; ++j) st[j][i] = min(st[j][i-1], st[j + (1 << (i-1))][i-1]);
	}
}
signed main() {
	scanf("%s", s); n = strlen(s);
	SA(); ST(); Manacher(); write(ans);
	return 0;
}
2025/1/9 22:35
加载中...