#!/usr/bin/python
# References:
# https://tarokuriyama.com/projects/palindrome2.php

# Transform S into T.
# For example, S = "abba", T = "^#a#b#b#a#$".
# ^ and $ signs are sentinels appended to each end to avoid bounds checking
class Solution(object):
    def longestPalindrome(self, s):
        T = '#'.join('^{}$'.format(s))
        print(T)
        n = len(T)
        P = [0] * n
        C = R = 0
        for i in range (1, n-1):
            print("i-"+str(i)+" =>, T: " + str(T[i])) + ', P:' +str(P[i])
            # If P[i'] <= R-i Means we can use Symetric Properties.
            # Else P[i'] expands beyound the left boundary of current palindrome.
            # Then we use R-i as we know Symetric till atleast right boundary.
            # We have to do character matching by expanding past the right edge (R).
            P[i] = (R > i) and min(R - i, P[2*C - i]) # equals to i' = C - (i-C)
            if P[2*C - i] > (R - i): print "P[i'] exceeds Left Boundary, Using (R-i) => P: "+str(P[i])
            # Attempt to expand palindrome centered at i
            while T[i + 1 + P[i]] == T[i - 1 - P[i]]: # While values +1,-1 of i matches.
                P[i] += 1 # Keep incresing the value of P at current i. [Expanding]
                # print "Expanding => P:"+str(P[i])
            # adjust center based on expanded palindrome. 
            # NOTE: i starts with 1 so it will always adjest center at i=1.
            if i + P[i] > R: # If palindrome centered at i expand past R,
                C, R = i, i + P[i]
                print "Adjecting the Center and Right"+" => C:"+str(C)+", R:"+str(R)
        # Find the maximum element in P.
        maxLen, centerIndex = max((n, i) for i, n in enumerate(P))
        return s[(centerIndex  - maxLen)//2: (centerIndex  + maxLen)//2]       

if __name__ == '__main__':
    s = "abaabba"
    obj = Solution()
    longestPalindrome = obj.longestPalindrome(s)
    print "Input String: "+ s
    print "Longest Palendrone is: "+str(longestPalindrome)+", with length: "+str(len(longestPalindrome))

# Notes: 
# P[i] is a list containing the expansion (int value on both sides) of respective value of T[i]
# C is the center, R is the right boundary of expansion.
# The iterations i starts with 1 so first time it always goes into if condition.
# Which results in initial shifting of center and right marker values.

# Algo:
# 0) PreProcess: Add ^[char]#[char]$ using T = '#'.join('^{}$'.format(s)).
# 1) Symetric Inference: If P[i'] <= R-i : P[i] = P[i'] else P[i] = R-i # Exceeded Left boundary.
# 2) Expansion: While values(T[i]) around current i T[i+(1...)] == T[i-(1...)] increase value of P.
# 3) Adjest: If Expansion centered at i expand past R (Right Boundary) adjest Center and Right
# 4) Get max expansion value and center_index [-max_exp][center][+max_exp] gives result. 

# Output
# ^#a#b#a#a#b#b#a#$
# i-1 =>, T: #, P:0
# P[i'] exceeds Left Boundary, Using (R-i) => P: False
# Adjecting the Center and Right => C:1, R:1
# i-2 =>, T: a, P:0
# P[i'] exceeds Left Boundary, Using (R-i) => P: False
# Adjecting the Center and Right => C:2, R:3
# i-3 =>, T: #, P:0
# i-4 =>, T: b, P:0
# P[i'] exceeds Left Boundary, Using (R-i) => P: False
# Adjecting the Center and Right => C:4, R:7
# i-5 =>, T: #, P:0
# i-6 =>, T: a, P:0
# i-7 =>, T: #, P:0
# Adjecting the Center and Right => C:7, R:11
# i-8 =>, T: a, P:0
# i-9 =>, T: #, P:0
# i-10 =>, T: b, P:0
# P[i'] exceeds Left Boundary, Using (R-i) => P: 1
# i-11 =>, T: #, P:0
# Adjecting the Center and Right => C:11, R:15
# i-12 =>, T: b, P:0
# i-13 =>, T: #, P:0
# i-14 =>, T: a, P:0
# i-15 =>, T: #, P:0
# P[i'] exceeds Left Boundary, Using (R-i) => P: False
# Input String: abaabba
# Longest Palendrone is: abba, with length: 4