记录编号	577680	评测结果	AAAAAAAAAAAAAAA
题目名称	[POI 2012]Prefixuffix	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.189 s
提交时间	2022-11-21 08:28:28	内存使用	8.59 MiB

// Problem: P3546 [POI2012]PRE-Prefixuffix
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3546
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
 
#include <bits/stdc++.h>
 
const int mod = 127237991;
const int maxn = 1e6 + 5;
const int p = 131;
char s[maxn];
int n,hash[maxn],pw[maxn];
 
int check(int x,int y,int l,int r) {
	return (hash[y] - 1ll * hash[x - 1] * pw[y - x + 1] % mod + mod) % mod
	== (hash[r] - 1ll * hash[l - 1] * pw[r - l + 1] % mod + mod) % mod;
}
 
int main() {
	freopen("prefixuffix.in","r",stdin);
	freopen("prefixuffix.out","w",stdout); 
	scanf("%d %s",&n,s + 1);
	pw[0] = 1;
	hash[0] = 0;
	for(int i = 1;i <= n;++ i)
		pw[i] = 1ll * pw[i - 1] * p % mod,
		hash[i] = (1ll * hash[i - 1] * p + s[i]) % mod;
	int ans = 0;
	for(int i = n / 2,p = 0;i;-- i) {
		p += 2;
		for(;p > 0&&((i + p) * 2 > n||!check(i + 1 , i + p , n - i - p + 1 , n - i));-- p);
		if(check(1 , i , n - i + 1 , n))
			ans = std::max(ans , i + p);
	}
	printf("%d\n",ans);
	return 0;
}