fork download
copy 
  1. /**
  2. 	Template by Akikaze (秋風) - formerly proptit_4t41.
  3. 	Code written by a random fan of momocashew and Chiho.
  4.  
  5. 	H△G x Mili - November 27th, 2013
  6. 	Mag Mell (Mili) - Sep 17th, 2014
  7. 	H△G x Mili Vol.2 - May 9th, 2015
  8. 	Miracle Milk (Mili) - Oct 12th, 2016
  9. 	青色フィルム (H△G) - February 14th, 2018
  10. 	Millennium Mother (Mili) - April 25th, 2018
  11. **/
  12.  
  13. /** -----PRAGMA----- **/
  14. #pragma comment(linker, "/stack:200000000")
  15. #pragma GCC optimize("Ofast")
  16. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  17.  
  18. #include <bits/stdc++.h>
  19. using namespace std;
  20.  
  21. /** -----BASIC MACROES----- **/
  22. #define endl '\n'
  23. #define i64 long long
  24. #define ld long double
  25. #define pub push_back
  26. #define mp make_pair
  27. #define fi first
  28. #define se second
  29. typedef vector<i64> vi;
  30. typedef vector<ld> vd;
  31. typedef vector<string> vs;
  32. typedef vector<bool> vb;
  33. typedef pair<i64, i64> pii;
  34. typedef pair<i64, pii> pip;
  35. typedef pair<pii, i64> ppi;
  36. const long long MOD = 1000000007LL, INF = 1e9, LINF = 1e18;
  37. const long double PI = 3.141592653589793116, EPS = 1e-9, GOLD = ((1+sqrt(5))/2);
  38. vi HashMod = {1000000007LL, 1000000009LL, 1000000021LL, 1000000033LL};
  39.  
  40. /** -----BIT CONTROLS----- **/
  41. template<class T> int getbit(T s, int i) { return (s >> 1) & 1; }
  42. template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
  43. template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
  44. template<class T> int cntbit(T s) { return __builtin_popcount(s); }
  45.  
  46. /** -----IDEAS/ALGORITHMS-----
  47.  
  48.     -------------------------- **/
  49.  
  50. /** -----CUSTOM TYPEDEFS/DEFINES----- **/
  51.  
  52.  
  53. /** -----GLOBAL VARIABLES----- **/
  54. i64 N, Base = 257, res = -1; string S, R;
  55. vector<vi> hashS, hashR, powBase;
  56.  
  57. /** -----EXTENSIVE FUNCTIONS----- **/
  58. void GenerateHashVal() {
  59. 	for (i64 i=1; i<N; i++) {
  60. 		for (i64 j=0; j<4; j++) {
  61. 			powBase[i][j] = (powBase[i-1][j] * Base) % HashMod[j];
  62. 		}
  63. 	}
  64. 	for (i64 i=0; i<N; i++) {
  65. 		for (i64 j=0; j<4; j++) {
  66. 			if (i == 0) {
  67. 				hashS[i][j] = ((i64)int(S[i]) * powBase[i][j]) % HashMod[j];
  68. 				hashR[i][j] = ((i64)int(R[i]) * powBase[i][j]) % HashMod[j];
  69. 			}
  70. 			else {
  71. 				hashS[i][j] = (hashS[i-1][j] + ((i64)int(S[i]) * powBase[i][j]) % HashMod[j]) % HashMod[j];
  72. 				hashR[i][j] = (hashR[i-1][j] + ((i64)int(R[i]) * powBase[i][j]) % HashMod[j]) % HashMod[j];
  73. 			}
  74. 		}
  75. 	}
  76. }
  77.  
  78. bool match(i64 stS, i64 enS, i64 stR, i64 enR) {
  79. 	for (i64 i=0; i<4; i++) {
  80. 		i64 valS = hashS[enS][i], valR = hashR[enR][i];
  81. 		if (stS > 0) {
  82. 			valS -= hashS[stS-1][i]; while (valS < 0) valS += HashMod[i];
  83. 		}
  84. 		valS *= powBase[max(stS,stR)-stS][i]; valS %= HashMod[i];
  85. 		if (stR > 0) {
  86. 			valR -= hashR[stR-1][i]; while (valR < 0) valR += HashMod[i];
  87. 		}
  88. 		valR *= powBase[max(stS,stR)-stR][i]; valR %= HashMod[i];
  89. //		cout << "valS = " << valS << endl;
  90. //		cout << "valR = " << valR << endl;
  91. 		if (valS != valR) return false;
  92. 	}
  93. 	return true;
  94. }
  95.  
  96. /** -----COMPULSORY FUNCTIONS----- **/
  97. void VarInput() {
  98. 	//ios_base::sync_with_stdio(0); cin.tie(NULL);
  99. 	cin >> N >> S; R = S; reverse(R.begin(), R.end());
  100. 	hashS.resize(N, vi(4, 0)); hashR.resize(N, vi(4, 0)); powBase.resize(N, vi(4, 1));
  101. }
  102.  
  103. void ProSolve() {
  104. 	GenerateHashVal();
  105. 	i64 top = 0, bot = N / 2;
  106. 	while (top <= bot) {
  107. 		i64 z = (top + bot) / 2;
  108. 		i64 ans = z * 2 + 1;
  109. //		tracker3(ans, top, bot);
  110. 		i64 flag = false;
  111. 		for (i64 i=0; i<=N-ans; i++) {
  112. 			i64 stS = i, enS = i+ans-1;
  113. 			i64 stR = N-1-enS, enR = N-1-stS;
  114. 			if (match(stS, enS, stR, enR)) {
  115. 				flag = true; break;
  116. 			}
  117. 		}
  118. 		i64 q = top, r = bot;
  119. 		if (flag) {top = z + 1; res = max(res, ans);} else bot = z;
  120. 		if (q == r) break;
  121. 	}
  122. 	top = 1; bot = N / 2;
  123. 	while (top <= bot) {
  124. 		i64 z = (top + bot) / 2;
  125. 		i64 ans = z * 2;
  126. 		//tracker3(ans, top, bot);
  127. 		i64 flag = false;
  128. 		for (i64 i=0; i<=N-ans; i++) {
  129. 			i64 stS = i, enS = i+ans-1;
  130. 			i64 stR = N-1-enS, enR = N-1-stS;
  131. 			if (match(stS, enS, stR, enR)) {
  132. 				flag = true; break;
  133. 			}
  134. 		}
  135. 		i64 q = top, r = bot;
  136. 		if (flag) {top = z + 1; res = max(res, ans);} else bot = z;
  137. 		if (q == r) break;
  138. 	}
  139. 	cout << res;
  140. }
  141.  
  142. /** -----MAIN FUNCTION----- **/
  143. int main() {
  144. 			#ifdef Akikaze
  145. 			//freopen("FILE.INP", "r", stdin);
  146. 			//freopen("FILE.OUT", "w", stdout);
  147. 			#endif
  148. 	VarInput();
  149. 			#ifdef Akikaze
  150. 			auto TIME1 = chrono::steady_clock::now();
  151. 			#endif
  152. 	ProSolve();
  153. 			#ifdef Akikaze
  154. 			auto TIME2 = chrono::steady_clock::now();
  155. 			auto DIFF = TIME2 - TIME1;
  156. 			cout << "\n\nTime elapsed: " << chrono::duration<double>(DIFF).count() << " seconds.";
  157. 			#endif
  158. 	return 0;
  159. }
  160.  
  161. /**
  162. OOO###$-^`^^.--~~~-.~~~~~-.^~~~~__~:++;+;~^^^^-!%eiiio?O##?i==e####!iiiii:.^^
  163. ##OO##$-^`^^.-~~~~~..~~~~~.^~~~~__~:+;;;;~^``^-*!!**o*e$##!=++*O###e=====:.^^
  164. ##OOOO$-^```.~~~~~~..~~~~~.^~~~~-_~:+;;;;~```^-e!eee**e$##!+;;oO###*====+_^^^
  165. ###OOO$_^```^~~~~~~..~~~~~.^.~~~-_~:+;;;;.```^-?!ee***e$##e;;;oO###*+++++_^`^
  166. ######O_^```^~~~~~~.......^^...~--~:;::::.````~ee***ooe$##e;::iO##Oo+++++-^``
  167. ####O$%_^```^.^^^^^^^^^^^^^^^^^^....~~~~~.````~;;:::::;=ii+_-_;o***+:::::-^`^
  168. O$$O$%e-^```^^.~....^.....^^.....^^.^^^^^^````^......^....................^``
  169. i++iiee-^```^.-;__:_.-:__:~._:-__..-----.^````^~-~~-~.~-~~-..~~~~..~~~~~.^^``
  170. :::;;i=-^```^.-;_-;_._;__;-.:;_:;~~::_:_.^````^-:__;-._;_:;~~___;-.__-::.^^``
  171. +;;;=i;~^````^-_--_-.-_--:~._:-__.~__-__.^````^~_--:-.-_-::.~_--:-.__-__.^^``
  172. ii=io*+~^````^-:--:-.-:__:-.__-__.._--_-.^````^~_--_~.---__.~_--:~.__-__.^```
  173. ee*e!!o-^````^-:_-:_._;__;-._:-::.~:_-;_.`````^-;__:-._:-::.~;__;-._:_;:.^```
  174. ??????e_^````^~~~~-~.~-~~-~.--~--.._--_-.^````^~_--_~.-_-__.~:--:~.__-:_.^```
  175. %%%??%!;^````^^^^^^^^^^^^^^^^^^^^^^^^...^^````^......^.....^......^.....^^```
  176. %%%%?%%o~`````````````````````````````^``````^^``^^^^^^^``^^^^^^^^^^^^^^^^```
  177. $$$$%%$!:^``````````````````````````````````^^```````````````````````````````
  178. #OOOOO$%o~````````````````````````````^^^^^..^`^^^..^``````````````````^^^^^^
  179. #####OO$!_^``^^^^^`^...^^``````````._+++++-~-.^.^..-.^````````````````^..~--:
  180. O######O%:...-____-_::_-~~~~-~.~~~_=ioo*eo===;_~.~~--~^^^^^^^^^^^^^^^^~--__::
  181. OOOOO##!:~^^.;!!?????o;__++===o*i:;+ii*!**oooi==;:_--:_:+=iii====;:;;__:+;__:
  182. OO%%$O#e~^^^^:!!$OOO?e=:__;+::_*=ii===oo**e***o*ooi;_--:=?%!!!!eo;:+;__;++;:;
  183. #O%?%$OO+.^`^:?%%##$i;::::_____oe!!?e*==oo*e**ee!?**+-_:_=oe!ee?=;;+;;;++::+=
  184. ##OO$%$O%_..~+??!%O?+;______:_=!?!$$?%!eo*****?!$!?!e+;:_:;o*o*!i;:;;+=+:_:;+
  185. #OO$?!?%$eiio*ooi==+::_:__;::;!%$$O$$$$%!e***!!$!%O$!oi:_;;ooiio*+;==+i+;+=ii
  186. $$?e*o*e!!!*o=;::;:_-__:::-::o$OOOOO#OO$$%!!ee%?O#$!!o+;::+i=+++=;++;+=+=i==o
  187. %?!*i=ioooo=+;:_:+=:__-___-_:%O#OOO###OOO%%%$$$OO$?%%=-_::_::;::::;;::::++++*
  188. OO%?*+;=o!e*o=+;;==:__:__--_iOO#######O#OOO##OO$$%$O?+_.:__;;;--;=i=++===++o!
  189. #O!i+;;:;+;:;+==o=:--_::::__?###O############O$OO#OO*+:.~__;=;--e$eo!!o*oiii=
  190. O?*=;:;;:_~~-~-_;__--_;:_::;O###############OO###OO!=;_-~-__i+__!O*+;:+ii=i_.
  191. ??!*=+=;;_-~~~-_:;+;_;+:_;;*##############&######O?*+:__----____ie=;_;+=+::.^
  192. e$e!*oi;:__--_:;::;;::+;:;i%#############&&######$!i;:_____-:;__=;-_::_:_~-~^
  193. *O?!ooi+;:_~-_---_;;::=+_;oO#####&####&#&&&#####?o+;:____;:__:-:+_--::__-.^^^
  194. *#Oe++;;__:~_;__:;;;+:+i;;o##########&##&&&&&&#%=;;:__;+;=;_-~~_--__+;:::.^^`
  195. eO$o+;::_;=+i=++;:-__;io;:*#########&##&##&&&&#e;::::=*%!o=:--:__::;++;+=:~^^
  196. eO%=;+===*e?%*=;:__:;+o!+_?#####OO####&#O#&&&#$i:::+o*=oo=::__;:_-+=+:+;_:_.^
  197. e$%=+oe*o?$?oo;-~~_:;o*e*e$#####OO######OO###O!=:_:=?%%*i+;;_--:+;o**;o=_~..^
  198. e$%e**!*?%!;-_i+-~_++**oe?$O###OO####&&##%$#O%*;:___i?$o+:;_-~_oiii=eieo=;-^^
  199. !$%!e!ee!?i++_:;+;===o*o=$####OO##&&&&&%O??$%?o;__-~-==_:_;=:;++i++io!$!+:-^`
  200. !%?*o!!ii+_==::;i=;e!*e*?O######&&&&&#&%??!?%?i;:__-~-----;e=:+====*!*!%;~.~^
  201. e%?*ioi*!++*?oo=e*;ooieo?O###O#&&&&&&&&%!!e??e=;;;;:_--_~:;=__+;;:;e!*+!i.^~.
  202. e%?eoi+o***e!e%!$%ii****%O#####&&&&&&&&Oeeee!o+++;+=+_-:~:;_-::_;;;oi;_=i~^^^
  203. !?!!??*=ie?ooe?oo=_-:i*!O#####&&&&&&&&&##$e*o=;;++=++:;_:;i;+;+io+;ii;~_;;_:;
  204. !ee?$%i=o!i+=*!ei-_::;;?O####&&&&&&&&&&##$ei=+;;+++=+;oi*=;-i*=**++oi:~~_;;=o
  205. !?!%$?=o?%o*%e!%=_+==++?OO###&&&&&&&&&&#O$!i=+;;++==i+oe=:+:??oo*===+;-.~_+*!
  206. !%?%O!i?#O###$%$!e!*=+*$O###&&&&&&&&&&&#$$!o=++++==ii=;io+i*%!oooi==i::~~~_!%
  207. e??%$?=i%###Oo*%$!o*ee?$####&&&&&&&&&&&#$%?*i=====iooeoo==oeeooo+!?!oo=:___*$
  208. e?%%%?==!###?=e$!o=o%$$O###&&&&&&&&&&&&#$??eo====ioo!?*i+=oi=++o!eeoi=~:;;:+!
  209. e?%$$%o*$###O!%?eo*e$%$####&&&&&&&&&&&&O???e*i==iio*o*o+====*!+o$!oi=_^.-:===
  210. ?%$##O%%O####OO%?i*%$$O###&&&&&&&&&&&&#$!??!eoiiio**iiiio*ooe$*?#!eii;-~_+oi=
  211. %%$#&#OO#######O!!%?$O###&&&&&&&&&&&&&O?e!?!e*oio*ooi+++o!e!e$?$O?!+i****ee*o
  212. ??$###OOOOO####$!$$%$?###&&&&&&&&&&&&&%!*e?!e*iiioooi;:=ie?%%$O!%e*+o?%?*ooii
  213. e%O#&#O$OOO$O##O$OO$!?##&&#&&&&&&&&&&O?**e!!e?%oiiioo-_:+??$%%?=o!o+:+i+:_---
  214. ?$O###OOO#$?%O##O$OO$O##&#&&&&&&&&###%e*o*ee!%**%e:i=.:=*??%?!?eoei:-_:_~~~..
  215. O$$OO##O##$!e%OO$$OO$##&###&&##&####%!*oo*ee%%%%$?i*e=o;oe!%?ie!o*=:___----~~
  216. #$%?!?O#O%%!e!%$%!!$O##&##&&####O##%eoiio**??!%$#O%!!*ei;=;i?e??e*i=++;;;++::
  217. #Oe-.:$#$%?????!!o=?##&&#&&###O$##!i+==io**?%?$$O#%??!=i=+:-o%O%!o!%?!e!!?!ee
  218. O?-``:%$$%%%??%?!=i$O#&##&&#&O?$%=--_;+=o*?%??O%OOO?e?iioi!o*%O%?o?%%%$$$$$$$
  219. ?_``~o!???!!!!!ee*!OO#&##&##%??+.``^~_;+i*O$OOO$$OO%%?e*ie%%e%O?eo?e!$O$?!%$$
  220. :` .+e!!eeeeeee**!!O#&#&&&#$?+.     `._:+=o*$OOO%%$%$$?*;o%?*!?*=e$$$###$$OOO
  221. ^ ^::i!e*o****e**!!$##&&&#O?-^       ``~_:_*$OOOOOOOO?!!;ie!io!*i?O##########
  222. ``_o;=*ooooo*****ee$#&&&&#?.`         ``^~-_%$OO#OOOOe*$?*o!io!=i!%OOOOO$$%$$
  223. ~_i*+oooooooo**o*ee$##&&##-.           ```.~*$$$OOOOO?o?$!o*i*o+o!%%?%%%????%
  224. i;=i+iooooiioo**ee!$#&&&#e^             ``^^:$?$O$%OO$e!$?=+io==ee???????!!!?
  225. ?;_+=i=iooiioo**e!!O&&&&#:`              `^^^?OOO$?$OO%e?ei+i**oo*eeeee******
  226. ?*;;=iiiiiiioio**!!O&&&&?^ `       ```   ``^^:OO$O$OO$O$?i++io*==iooooooooooo
  227. ?*++=iiiiooioi**e!?O&&&&+```    ~=^-____~```^^*OOO##O$%$?o*!i=iiiiiiiiiiiii==
  228. ?o+=oiioooioo****!%#&&&O.`^`    -=_---_;+;^``^.%O####O$!!!?!i=i========++++++
  229. !i=ioooiooo**e!e!?%#&&&*`^``` ``    `    .:.```;O####OO?!??!==i==++++;;;;;;;;
  230. *=io*oooi*e!!???%$O#&&#-^.`````` ```..^^`` .^```e##OO$$%?!*o+===+;;:::::::___
  231. oooeeee**!!%%%?%$O##&&?^.^`````^  `~.^^^`^.`````.$OOOO$**?!ooi=+;::_____-----
  232. ee*eee!?%%%$$$%$OO#&&&+^.^`````^^`~~.^.^``.~^^```+OO#O$oe%*ioo++;::___:_-----
  233. e*o**e?%%$%$OOO$$O#&&#~^.^^^^``^.~-....^``.~.~````?##O$e?%*+ii++;;::::;::____
  234. eooo*%OOO#####OO$O#&&$^^.^^^``^^~-~....^^`^~~~^```_O#O$?%$$io=;;;;;;;;;;;;;::
  235. *oo*!O#######O$%$O#&&e^..^^^`^^^.~.....^^`^.~~~^```*#O$%%O#$e;:;;;;:::_::____
  236. *oe??%$%$%?%%%??%$##&i`..^^^^^^^.~.~...^``^.~~-.```.OO%%$O##!;_;+;:__-~--~~~~
  237. *i*e*eeee!!!!e!!%%#O#+^^.....^^^.~.~~..^``^^.~-~^```+%$%?$##!;_;+;;:_~~-_-~~~
  238. *ioe*ee*!!e!!e!!%$O?#+^^...~.^^^.~~~~.^```^^.~~-~```.%$?!$OO!;_;++;:_-~---~~~
  239. o=ie*e**!e*ee*e%$##?#+`^..~~^^^^.~~...^```^^^.~--^```!%!%%OO?+:;++;;:_-~--~~~
  240. o==**e*e!e*e?!oeO#O$&=``^.~~^^^.~~~...^` ``^^.~~~~```o%?%!?%?=::;;;;:-~~~~~~~
  241. *i=*!e*eeeeee?%%O$$##=^`^.~.^^..~~~..``````^^^~~~~^``=$?%%%$$?i;++++;-~--~~~~
  242. !oie!!e!!**eoo?%$####=_`^.~^....~~....~--_~.~....~~``~%*i!?!**i=====+:-::-~~~
  243. !*ie!**!!***ooe%%#&&&i:.^^.^^..^.~~~__--:;;..~..~~~.``ee=***=iooiii==+++:-~~~
  244. $?eeeoo!*ooi=i**io#&&e_~^^.^^..~::::__~-:::.-~-~+.~.^`iO$$$$???!!i=+++==;--~~
  245. $%??*o*eo+oooi*o;i$O&$--^^.^^._::__:____::_.~--~*~..^^+####OO?%%?+;::;;;:----
  246. !???!!!*oieo==*=;;+=e#:-.^^^.:___-_:__::__-~-.~~oi.^..;######$??e:______-----
  247. ??%?!e!eeee*ii*=;+=++*+_.^^.:__--------_-_.~-~--;?-..~+O######$%!:___--------
  248. !!??ee?!ee*oii+;++i+;+i:-.._:-_--_-__--_--^~~.~-.**..-iO##O####$?:_______----
  249. e!%?eee*o*o====+++=+;+i:;~.;_-_~~--------~^~-~.-.-!:~-*#OOO##O#$!+;;;:;;;:::_
  250. ee??!eiii*oi==*=+;==+=o=;:~+_:_.~--~~~~~~..~~~.-~.i*.-*OOO#O##OOo=ii======+++
  251. !**e!!oii*oi=o*+;;====oi;+-+::-~--~~~~~~~^.~~~.-~-~!:_eOO######Oe=iii=====+++
  252. ?!**ee*oo*ii=oo;:;==+=*o+;:=;;_~~~~~~~~~~^~~~~.-~_~o=_!#OO#####O$o======+++++
  253. ?*ii!eoooi===oi;;:+++=**o++=;;_.~~~~~....^.~~~.~~:_;o_?#OOOO###O%i+++++++++;;
  254. !iii!oiooi==ioi===iiio*oi=+o=;_~~~~~~...^.~~~~.~~:_-o_%OOOO###OO%i;;;;;;;;;;;
  255. !**e!ooo**iio*o+;+ii==iooo==o;:.~~~~~...^..~~~..~_:_=_$O#OOO##OO$e;;;::;;;:::
  256. e**e*i=ioii=o!*i++===+ioi*i=o+:~~~~~~...`..~~~..~:;;+:OO#OOOOO##O%+::::::::__
  257. ee*!oi=ioiii*!!o++==i=oooooi==;~~~~~~...^...~...-;;+;+$$O####O#OO$+::________
  258. *oe*=iiooi=i*e*i==oi=+=ioi=ii+;~~~~~...^^...~~..-;+*;*OOO#######$%=::________
  259. io!i+io**i=ie*i===ii==oe!ee?i=;-~~~....^^......._;e*;%OOO#####O#O$*;:;:______
  260. =ie*ii=ii==ie*=++;=i=i**ee!?!i=_~~~....^........:;O*i$##OOO#O#O##O$+:;::_____
  261. iiooii=i==io**=;;;====io*eeeeoi:-~~....^.....~..;=#!oOO##OOOO###O#Oi;;:__---_
  262. **/
  263.  
  264. // Tribute to a friend I owe countless. Thanks, TN.
Success #stdin #stdout 0s 4192KB
comments (?)
stdin
copy 
5
abacd
stdout
copy 
3
https://ideone.com/EmdeyZ
VNSPOJ-PALINY (Multiple)
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!