Longest Palindrome Subsequence，最长回文子序列（LPS）

def get_lcs_bu(a, b):
    alen = len(a)
    blen = len(b)
    pos = [['^']*blen for _ in range(alen)]
    rec = [0] * (blen+1)
    for i in range(alen):
        c = rec[:]
        for j in range(blen):
            if a[i] == b[j]:
                rec[j+1] = c[j] + 1
                pos[i][j] = '\\'
            else:
                if rec[j] >= c[j+1]:
                    rec[j+1] = rec[j]
                else:
                    rec[j+1] = c[j+1]
                    pos[i][j] = '<'
    #
    r = rec[j+1]
    lcs = ''
    i = alen - 1
    j = blen - 1
    while not (i<0 or j<0):
        if pos[i][j] == '\\':
            lcs += str(a[i])
            i -= 1
            j -= 1
        elif pos[i][j] == '^':
            j -= 1
        else:  # '<'
            i -= 1
    return r, lcs[::-1]


class palindrome:  # dummy code

    def __init__(self, s):
        self.s = s
        self.slen = len(s)
        self.rec = {}

    def _rlcs(self, p, q):  # include q, but not p
        if p<=0 or q>=self.slen:
            return 0
        if (p,q) in self.rec:
            return self.rec[p,q]
        r = 0
        for i in reversed(range(p)):
            for j in range(q,self.slen):
                if self.s[i] == self.s[j]:
                    r = max(r, 2+self._rlcs(i,j+1))
                    break
        self.rec[p,q] = r
        return r

    def mps(self):
        ans = 0
        for i in range(self.slen):
            while i < self.slen:
                r = 1
                j = i+1
                while j<self.slen and self.s[j]==self.s[i]:
                    j += 1
                    r += 1
                r += self._rlcs(i,j)
                ans = max(ans, r)
                i += 1
        return ans


a = 'banana'
pa = palindrome(a)
print(pa.mps())
print(get_lcs_bu(a,a[::-1]))

a = 'abc123c4b5a'
pa = palindrome(a)
print(pa.mps())
print(get_lcs_bu(a,a[::-1]))

a = 'abc66666a'
pa = palindrome(a)
print(pa.mps())
print(get_lcs_bu(a,a[::-1]))

a = 'geeksforgeeks'
pa = palindrome(a)
print(pa.mps())
print(get_lcs_bu(a,a[::-1]))

5
(5, 'anana')
7
(7, 'abc3cba')
7
(7, 'a66666a')
5
(5, 'eegee')

def lcs_bu(a, b):
    alen = len(a)
    blen = len(b)
    rec = [0] * (blen+1)
    for i in range(alen):
        for j in range(blen):
            if a[i] == b[j]:
                rec[j+1] = rec[j] + 1
            else:
                rec[j+1] = max(rec[j], rec[j+1])
    return rec[blen]


def lps_bu(s):
    n = len(s)
    rec = [0] * (n+1)
    for i in reversed(range(n)):
        for j in range(n):
            if s[j] == s[i]:
                rec[j+1] = rec[j] + 1
            else:
                rec[j+1] = max(rec[j], rec[j+1])
    return rec[n]


for a in ('abc12333cba', 'geeks44geeks', '12333'):
    print(lcs_bu(a,a[::-1]))
    print(lps_bu(a))