Given a string, find the longest substring which is palindrome in Linear time O(N).
Input:
The first line of input contains an integer T denoting the no of test cases . Then T test cases follow. The only line of each test case contains a string.
Output:
For each test case print the Longest Palindromic Substring. If there are multiple such substrings of same length, print the one which appears first in the input string.
Constraints:
1 <= T <= 100
1 <= N <= 50
Example:
Input:
2
babcbabcbaccba
forgeeksskeegfor
Output:
abcbabcba
geeksskeeg
 
 
 
Note:The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures
Skill types: Data structures

Starter code:
#User function Template for python3

def LongestPalindromeSubString(text):
    # code here
    # return the longest palindrome substring


Solutions:
def manacher_odd(s):
	n = len(s)
	s = '$' + s + '^'
	p = [0] * (n + 2)
	(l, r) = (1, 1)
	max_len = 0
	pos = -1
	for i in range(1, n + 1):
		p[i] = max(0, min(r - i, p[l + r - i]))
		while s[i - p[i]] == s[i + p[i]]:
			p[i] += 1
		if p[i] > max_len:
			max_len = p[i]
			pos = i
		if i + p[i] > r:
			r = i + p[i]
			l = i - p[i]
	return s[pos - p[pos] + 2:pos + p[pos] - 1]

def LongestPalindromeSubString(text):
	s = '#' + '#'.join(list((c for c in text))) + '#'
	ans = manacher_odd(s)
	return ''.join(ans.split(sep='#'))


import sys

def UpdatedString(string):
	newString = ['#']
	for char in string:
		newString += [char, '#']
	return ''.join(newString)

def LongestPalindromeSubString(text):
	string = UpdatedString(text)
	LPS = [0 for _ in range(len(string))]
	C = 0
	R = 0
	for i in range(len(string)):
		iMirror = 2 * C - i
		if R > i:
			LPS[i] = min(R - i, LPS[iMirror])
		else:
			LPS[i] = 0
		try:
			while string[i + 1 + LPS[i]] == string[i - 1 - LPS[i]]:
				LPS[i] += 1
		except:
			pass
		if i + LPS[i] > R:
			C = i
			R = i + LPS[i]
	(r, c) = (max(LPS), LPS.index(max(LPS)))
	return string[c - r:c + r].replace('#', '')


def LongestPalindromeSubString(s):
	pairs = [0 for _ in range(2 * len(text) - 1)]
	longest = 1
	index = 0
	box = 0
	mirror = 0
	for i in range(1, len(pairs)):
		left_c = (i - 1) // 2
		right_c = (i + 2) // 2
		if right_c < box:
			identical = pairs[mirror - (i - mirror)]
			if right_c + identical > box + 1:
				identical = box + 1 - right_c
			right_c += identical
			pairs[i] = identical
			left_c -= identical
			if right_c <= box or right_c == len(text):
				continue
		while left_c >= 0 and right_c < len(text) and (text[left_c] == text[right_c]):
			left_c -= 1
			right_c += 1
			pairs[i] += 1
		if pairs[i] > 1 and right_c - 1 > box:
			box = right_c - 1
			mirror = i
		length = 2 * pairs[i]
		if i % 2 == 0:
			length += 1
		if length > longest:
			longest = length
			index = (i + 1) // 2 - length // 2
	return text[index:index + longest]


def LongestPalindromeSubString(text):
	if text == text[::-1]:
		return text
	elif len(text) == 1:
		return text
	original = text[:]
	text = '@#' + '#'.join(text) + '#$'
	n = len(text)
	C = 0
	R = 0
	max = 0
	maxInd = 0
	pal = [0] * n
	for i in range(1, n - 1):
		mirr = 2 * C - i
		if i < R:
			pal[i] = min(pal[mirr], R - i)
		while text[i + (1 + pal[i])] == text[i - (1 + pal[i])]:
			pal[i] += 1
		if pal[i] > max:
			max = pal[i]
			maxInd = i
		if i + pal[i] > R:
			C = i
			R = i + pal[i]
		if i + pal[i] == n - 2:
			break
	if maxInd % 2 == 0:
		halfLen = (pal[maxInd] - 1) // 2
		maxInd = maxInd // 2 - 1
		return original[maxInd - halfLen:maxInd + halfLen + 1]
	else:
		halfLen = pal[maxInd] // 2
		maxInd = (maxInd - 1) // 2
		return original[maxInd - halfLen:maxInd + halfLen]


def LongestPalindromeSubString(text):
	N = len(text)
	if N <= 1:
		return text
	N = 2 * N + 1
	L = [0] * N
	L[0] = 0
	L[1] = 1
	C = 1
	R = 2
	i = 0
	iMirror = 0
	maxLPSLength = 0
	maxLPSCenterPosition = 0
	start = -1
	end = -1
	diff = -1
	for i in range(2, N):
		iMirror = 2 * C - i
		L[i] = 0
		diff = R - i
		if diff > 0:
			L[i] = min(L[iMirror], diff)
		try:
			while (i + L[i] < N and i - L[i] > 0) and ((i + L[i] + 1) % 2 == 0 or text[(i + L[i] + 1) // 2] == text[(i - L[i] - 1) // 2]):
				L[i] += 1
		except Exception as e:
			pass
		if L[i] > maxLPSLength:
			maxLPSLength = L[i]
			maxLPSCenterPosition = i
		if i + L[i] > R:
			C = i
			R = i + L[i]
	start = (maxLPSCenterPosition - maxLPSLength) // 2
	end = start + maxLPSLength - 1
	if len(text[start:end + 1]) == 1:
		return text[0]
	return text[start:end + 1]


def LongestPalindromeSubString(text):
	if text == text[::-1]:
		return text
	maxlen = 0
	start = 0
	right = 0
	betalen = 2 * len(text) + 1
	betastr = '#'
	centre = 0
	p = [0] * betalen
	for i in text:
		betastr += i + '#'
	for i in range(1, betalen - 1):
		if i < right:
			p[i] = min(right - i, p[2 * centre - i])
		while betastr[min(betalen - 1, i + p[i] + 1)] == betastr[max(0, i - p[i] - 1)]:
			p[i] += 1
		if i + p[i] > right:
			right = i + p[i]
			centre = i
		if p[i] > maxlen:
			start = int((i - p[i]) / 2)
			maxlen = p[i]
	return text[start:start + maxlen]


def LongestPalindromeSubStringNaive(text):
	n = len(text)
	max_len = 1
	max_i = 0
	prev_indices = [0]
	for i in range(1, n):
		curr_indices = []
		for prev_index in prev_indices:
			curr_index = prev_index - 1
			if curr_index > -1 and text[i] == text[curr_index]:
				curr_indices.append(curr_index)
		if i - 1 > -1 and text[i] == text[i - 1]:
			curr_indices.append(i - 1)
		curr_indices.append(i)
		prev_indices = curr_indices
		curr_len = i - prev_indices[0] + 1
		if curr_len > max_len:
			max_len = curr_len
			max_i = prev_indices[0]
	return text[max_i:max_i + max_len]

def LongestPalindromeSubString(text):
	n = len(text)
	N = 2 * n + 1
	new_text = [''] * N
	for i in range(n):
		new_text[2 * i] = '#'
		new_text[2 * i + 1] = text[i]
	new_text[-1] = '#'
	center = 0
	max_right = 0
	max_len = 0
	P = [0] * N
	for i in range(1, N):
		if i < max_right:
			P[i] = min(max_right - i, P[2 * center - i])
		left_i = i - P[i] - 1
		right_i = i + P[i] + 1
		while left_i > -1 and right_i < N and (new_text[left_i] == new_text[right_i]):
			P[i] += 1
			left_i = i - P[i] - 1
			right_i = i + P[i] + 1
		if i + P[i] > max_right:
			center = i
			max_right = i + P[i]
		if P[i] > max_len:
			start = (i - P[i]) // 2
			max_len = P[i]
	return text[start:start + max_len]


def LongestPalindromeSubString(text):
	n = len(text)
	arr = '#'
	for i in range(n):
		arr += text[i]
		arr += '#'
	val = [0] * len(arr)
	center = 0
	right = 0
	longestCent = 0
	longestLength = 0
	for i in range(len(arr)):
		mirror = 2 * center - i
		if right > i:
			val[i] = min(val[mirror], right - i)
		a = i - (val[i] + 1)
		b = i + (val[i] + 1)
		while a >= 0 and b < len(arr) and (arr[a] == arr[b]):
			a -= 1
			b += 1
			val[i] += 1
		if val[i] > longestLength:
			longestCent = i
			longestLength = val[i]
		if i + val[i] > right:
			center = i
			right = i + val[i]
	return arr[longestCent - longestLength:longestCent + longestLength].replace('#', '')


def LongestPalindromeSubString(text):
	if len(text) == 1:
		return text
	s = '#'.join('^{}$'.format(text))
	n = len(s)
	L = [0] * n
	(C, R) = (0, 0)
	mLen = 0
	mLenPos = 0
	for i in range(1, n - 1):
		L[i] = R > i and min(L[2 * C - i], R - i)
		while s[i + L[i] + 1] == s[i - L[i] - 1]:
			L[i] += 1
		if L[i] > mLen:
			mLen = L[i]
			mLenPos = i
		if i + L[i] > R:
			C = i
			R = i + L[i]
	start = (mLenPos - mLen) // 2
	end = start + mLen
	return text[start:end]


def fastLongestPalindromes(seq):
	seqLen = len(seq)
	l = []
	i = 0
	palLen = 0
	while i < seqLen:
		if i > palLen and seq[i - palLen - 1] == seq[i]:
			palLen += 2
			i += 1
			continue
		l.append(palLen)
		s = len(l) - 2
		e = s - palLen
		for j in range(s, e, -1):
			d = j - e - 1
			if l[j] == d:
				palLen = d
				break
			l.append(min(d, l[j]))
		else:
			palLen = 1
			i += 1
	l.append(palLen)
	lLen = len(l)
	s = lLen - 2
	e = s - (2 * seqLen + 1 - lLen)
	for i in range(s, e, -1):
		d = i - e - 1
		l.append(min(d, l[i]))
	return l

def LongestPalindromeSubString(text):
	l = max(fastLongestPalindromes(text))
	for i in range(len(text) - l + 1):
		substr = text[i:i + l]
		if substr == substr[::-1]:
			return substr
	return ''


def LongestPalindromeSubString(text):
	s = ['#']
	for i in text:
		s += [i, '#']
	s = ''.join(s)
	n = len(s)
	lps = [0 for i in range(n)]
	c = 0
	r = 0
	for i in range(n):
		im = c - (i - c)
		if r > i:
			lps[i] = min(r - i, lps[im])
		else:
			lps[i] = 0
		try:
			while s[i - 1 - lps[i]] == s[i + 1 + lps[i]]:
				lps[i] += 1
		except:
			pass
		if r < i + lps[i]:
			c = i
			r = i + lps[i]
	(r, c) = (max(lps), lps.index(max(lps)))
	k = s[c - r:c + r]
	return k.replace('#', '')


def my_print(*args):
	pass

def LongestPalindromeSubString(text):
	n = len(text)
	N = 2 * n + 1
	maxLPSlen = 1
	maxLPScenter = 1
	L = [0] * N
	L[0] = 0
	L[1] = 1
	C = 1
	R = 2
	iMirror = 0
	for i in range(2, N):
		iMirror = 2 * C - i
		L[i] = 0
		diff = R - i
		expand = True
		if diff > 0:
			L[i] = min(L[iMirror], diff)
		if expand:
			while i + L[i] < 2 * n and i - L[i] > 0:
				if (i + L[i] + 1) % 2 == 0:
					L[i] += 1
				elif text[(i + L[i] + 1) // 2] == text[(i - L[i] - 2) // 2]:
					L[i] += 1
				else:
					break
		if L[i] > maxLPSlen:
			maxLPSlen = L[i]
			maxLPScenter = i
		if i + L[i] > R:
			C = i
			R = i + L[i]
	start = (maxLPScenter - maxLPSlen) // 2
	end = (maxLPScenter + maxLPSlen) // 2 - 1
	res = text[start:end + 1]
	return res