"""
======================================
(C) abs|Zer0| Nov 2010
======================================
Practice Dynamic Programming
Longest palindromic subsequence

+Given string: x1,x2,....,xn

+ denotes m[i][j] : length of the longest palindromic subsequence
+ s: matrix for tracing the sequence

Recurrence Relation:
m[i][j]  = 1 if i = j (a character itself is a palindromic subsequence with length 1)
m[i][j]  = { * m[i+1][j-1] + 2 if xi = xj
             * max( m[i+1][j], m[i][j-1]) if xi <> xj

"""
import sys
st = "ILLINOISURBANACHAMPAIGN"
n = len(st)
m = [[0] * n for i in range(n)]  #define a matrix n*n with all set to 0
s = [["."] * n for i in range(n)]

#(a character itself is a palindromic subsequence with length 1)
for i in range(0, n):
    m[i][i] = 1
    s[i][i] = "/"

for x in range(1, n):
    for i in range(0, n):
    j = i + x
    if j < n:

        if st[i] == st[j]: # xi == xj here
        m[i][j] = m[i+1][j-1] + 2 # increase longest palindromic subsequence length by 2
        s[i][j] = "/" #trace path
        else:
        if m[i+1][j] >= m[i][j-1]:
            m[i][j] = m[i+1][j]
            s[i][j] = "^"
        else:
            m[i][j] = m[i][j-1]
            s[i][j] = ">"

#print out the longest palindromic subsequence string
def print_path(st, m, s, i, j):
    ret = [""] * m[i][j] #a return string is length of m[0][n]

    # 2 string pointers point to begin and end of the return string
    idx = 0
    idx2 = len(ret) - 1

    while True:
    if i > j:
        break
    if s[i][j] == '/': #if found 2 same chars
        ret[idx] = st[i] #append to the beginning and the end of the return string
        ret[idx2] = st[j]
        idx += 1  #move the pointer of return string
        idx2 -= 1

        i = i + 1 #move the pointer of the s matrix
        j = j - 1
    elif s[i][j] == '>':
        i = i
        j = j - 1
    else:
        i = i + 1
        j = j

    print ret #print out result

print_path(st, m, s, 0, n-1)