A palindrome is a string that reads the same from left to right as it does from right to left.

Given a string, $\mbox{S}$, of $N$ lowercase English letters, we define a $\boldsymbol{\mbox{k}}$-length rotation as cutting the first $\boldsymbol{\mbox{k}}$ characters from the beginning of $\mbox{S}$ and appending them to the end of $\mbox{S}$. For each $\mbox{S}$, there are $N$ possible $\boldsymbol{\mbox{k}}$-length rotations (where $0\leq k<N$). See the Explanation section for examples.

Given $N$ and $\mbox{S}$, find all $N$ $\boldsymbol{\mbox{k}}$-length rotations of $\mbox{S}$; for each rotated string, $S_{k}$, print the maximum possible length of any palindromic substring of $S_{k}$ on a new line.

Input Format

The first line contains an integer, $N$ (the length of $\mbox{S}$). 

The second line contains a single string, $\mbox{S}$.

Constraints

$1\leq N\leq5\times10^5$
$0\leq k<N$
$\textit{$S is complicated of lower case English letters.}

Output Format

There should be $N$ lines of output, where each line $\boldsymbol{\mbox{k}}$ contains an integer denoting the maximum length of any palindromic substring of rotation $S_{k}$.

Sample Input 0

13
aaaaabbbbaaaa

Sample Output 0

12
12
10
8
8
9
11
13
11
9
8
8
10

Sample Input 1

7
cacbbba

Sample Output 1

3
3
3
3
3
3
3

Sample Input 2

12
eededdeedede

Sample Output 2

5
7
7
7
7
9
9
9
9
7
5
4

Explanation

Consider Sample Case 1, where $S=\text{"cacbbba"}$. 

The possible rotations, $S_{k}$, for string $\mbox{S}$ are: 

$S_0=\text{"cacbbba"}$. 

$S_1=\text{"acbbac"}$ 

$S_2=\text{"cbbbea"}$ 

$S_3=\text{"bbacacac"}$ 

$S_4=\text{"bbacacab"}$ 

$S_5=\text{"bacacab"}$ 

$S_6=\text{"acacabb"}$        

The longest palindromic substrings for each $S_{k}$ are: 

$S_0:\text{"cac"}$ and $\text{"bbb}$, so we print their length ($3$) on a new line. 

$S_1:\text{"bbb"}$, so we print its length ($3$) on a new line. 

$S_2:\text{"bbb"}$ and $\text{"aca"}$, so we print their length ($3$) on a new line. 

$S_3:\text{"bbb"},\text{"aca"}$ and $\text{"cac''}$, so we print their length ($3$) on a new line. 

$S_4:\text{"aca''}$ and $\text{"cac''}$, so we print their length ($3$) on a new line. 

$S_5:\text{"aca''}$ and $\text{"cac''}$, so we print their length ($3$) on a new line. 

$S_6:\text{"aca"},\text{"cac"},$ and $\text{"bbb}$, so we print their length ($3$) on a new line.

Source: hackerrank | Difficulty: HARD
Tags: String algorithms


Solutions:
num = input()
word = input()
import sys
import random

def palin(s):
	container = []
	org = []
	contain = []
	ego = []
	conca = len(s)
	b = 3 * s
	curchar = '\x00'
	curstart = 0
	curcount = 0
	let = []
	tripstart = 0
	for (i, c) in enumerate(b):
		if not i:
			curstart = 0
			curcount = 1
			curchar = c
		elif c == curchar:
			curcount += 1
		else:
			for j in range(curcount):
				let.append((curchar, curcount, curstart))
			curstart = i
			curcount = 1
			curchar = c
	for i in range(curcount):
		let.append((curchar, curcount, curstart))
	for i in range(conca):
		c = conca + i
		part = -1
		if let[c][1] % 2 and c == let[c][2] + let[c][1] // 2:
			inner = let[c][1]
			mud = i
			part = let[c][1]
			p1 = let[c][2] - 1
			p2 = let[c][2] + let[c][1]
			while p1 >= 0 and p2 < 3 * conca and (let[p1][0] == let[p2][0]):
				if let[p1][1] != let[p2][1]:
					part += 2 * min(let[p1][1], let[p2][1])
					break
				part += 2 * let[p1][1]
				p1 -= let[p1][1]
				p2 += let[p2][1]
			tit = part
			org.append((tit, mud, inner))
		else:
			part = 1 + 2 * min(c - let[c][2], let[c][2] + let[c][1] - 1 - c)
		container.append(min(conca, part))
		egg = 0
		if let[c][1] % 2 == 0 and c == let[c][2] + let[c][1] // 2:
			inn = let[c][1]
			mid = i
			egg = let[c][1]
			p1 = let[c][2] - 1
			p2 = let[c][2] + let[c][1]
			while p1 >= 0 and p2 < 3 * conca and (let[p1][0] == let[p2][0]):
				if let[p1][1] != let[p2][1]:
					egg += 2 * min(let[p1][1], let[p2][1])
					break
				egg += 2 * let[p1][1]
				p1 -= let[p1][1]
				p2 += let[p2][1]
			tat = egg
			ego.append((tat, mid, inn))
		else:
			egg = 2 + 2 * min(c - 1 - let[c][2], let[c][2] + let[c][1] - 1 - c)
		contain.append(min(conca, egg))
	rock = sorted(org, key=lambda x: x[0], reverse=True)
	wrec = sorted(ego, key=lambda x: x[0], reverse=True)
	bests = []
	if conca % 2:
		bests = [max(container[(i + conca // 2) % conca], min(conca - 1, max(contain[(i + conca // 2) % conca], contain[(i + conca // 2 + 1) % conca]))) for i in range(conca)]
	else:
		bests = [max(contain[(i + conca // 2) % conca], min(conca - 1, max(container[(i + conca // 2) % conca], container[(i + conca // 2 - 1) % conca]))) for i in range(conca)]
	for i in range(conca):
		top = bests[i]
		rosi = 0
		while rosi < len(rock) and rock[rosi][0] > top:
			res = min(rock[rosi][0], 1 + 2 * min((rock[rosi][1] - i) % conca, (i - 1 - rock[rosi][1]) % conca))
			if res < rock[rosi][2]:
				res = min(rock[rosi][2], max((i - (rock[rosi][1] - rock[rosi][2] // 2)) % conca, (rock[rosi][1] + rock[rosi][2] // 2 + 1 - i) % conca))
			top = max(top, min(res, conca))
			rosi += 1
		resi = 0
		while resi < len(wrec) and wrec[resi][0] > top:
			res = min(wrec[resi][0], 2 * min((wrec[resi][1] - i) % conca, (i - wrec[resi][1]) % conca))
			if res < wrec[resi][2]:
				res = min(wrec[resi][2], max((i - (wrec[resi][1] - wrec[resi][2] // 2)) % conca, (wrec[resi][1] + wrec[resi][2] // 2 - i) % conca))
			top = max(top, min(res, conca))
			resi += 1
		bests[i] = top
	return bests
for i in palin(word):
	print(i)