제출 #46673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46673		aome	회문 (APIO14_palindrome)	C++17	47 / 100	806 ms	40168 KiB

palindrome

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 300005;
const int base = 404;
const int mod = 1e9 + 9;
 
int n;
int cnt;
int f[N];
int sz[N];
int pw[N];
int hsh[2][N];
long long res;
vector<int> G[N];
string s;
map<int, int> label;
 
inline int get0(int l, int r) {
	int ret = hsh[0][r] - 1LL * hsh[0][l - 1] * pw[r - l + 1] % mod;
	if (ret < 0) ret += mod; return ret;
}
 
inline int get1(int l, int r) {
	int ret = hsh[1][l] - 1LL * hsh[1][r + 1] * pw[r - l + 1] % mod;
	if (ret < 0) ret += mod; return ret;
}

inline int get2(int l, int r) {
	return 1LL * get0(l, r) * get1(l, r) % mod;
}

bool check(int l, int r) {
	return get0(l, r) == get1(l, r);
}
 
void go(int l, int r) {
	// cout << "# " << l << ' ' << r << '\n';
	int tmp, id, lst;
	tmp = get2(l, r), id = label[tmp];
	if (!id) {
		label[tmp] = id = ++cnt;
		sz[id] = r - l + 1, f[id]++;
		lst = id, l++, r--;
	}
	else {
		f[id]++; return;
	}
	while (l <= r) {
		tmp = get2(l, r), id = label[tmp];
		if (!id) {
			label[tmp] = id = ++cnt;
			sz[id] = r - l + 1;
			G[id].push_back(lst);
			lst = id, l++, r--;
		}
		else {
			G[id].push_back(lst);
			return;
		}
	}
	if (l > r) G[0].push_back(lst);
}
 
void dfs(int u) {
	for (auto v : G[u]) {
		dfs(v), f[u] += f[v];
	}
	res = max(res, 1LL * sz[u] * f[u]);
}
 
int main() {
	ios::sync_with_stdio(false);
	cin >> s, n = s.size();
	pw[0] = 1;
	for (int i = 1; i <= n; ++i) {
		pw[i] = 1LL * pw[i - 1] * base % mod;
	}
	for (int i = 1; i <= n; ++i) {
		hsh[0][i] = (1LL * hsh[0][i - 1] * base + s[i - 1] - 'a' + 1) % mod;
	}
	for (int i = n; i >= 1; --i) {
		hsh[1][i] = (1LL * hsh[1][i + 1] * base + s[i - 1] - 'a' + 1) % mod;
	}
	for (int i = 1; i <= n; ++i) {
		int l, r; 
		l = 1, r = min(i, n - i + 1);
		while (l < r) {
			int mid = (l + r + 1) >> 1;
			if (check(i - mid + 1, i + mid - 1)) l = mid;
			else r = mid - 1;
		}
		go(i - l + 1, i + l - 1);
		l = 0, r = min(i, n - i);
		while (l < r) {
			int mid = (l + r + 1) >> 1;
			if (check(i - mid + 1, i + mid)) l = mid;
			else r = mid - 1;
		}
		if (l) go(i - l + 1, i + l);
	}
	dfs(0);
	cout << res;
}

컴파일 시 표준 에러 (stderr) 메시지

palindrome.cpp: In function 'int get0(int, int)':
palindrome.cpp:22:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (ret < 0) ret += mod; return ret;
  ^~
palindrome.cpp:22:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (ret < 0) ret += mod; return ret;
                           ^~~~~~
palindrome.cpp: In function 'int get1(int, int)':
palindrome.cpp:27:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (ret < 0) ret += mod; return ret;
  ^~
palindrome.cpp:27:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (ret < 0) ret += mod; return ret;
                           ^~~~~~

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