Longest Palindrome Subsequence - rFronteddu/general_wiki GitHub Wiki

Given a word what is the longest palindrome subsequence.

0 1 2 3 4 5
a g b d b a

| - | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 3 | 5 |
| 1 | - | 1 | 1 | 1 | 3 | 3 |
| 2 | - | - | 1 | 1 | 3 | 3 |
| 3 | - | - | - | 1 | 1 | 1 |
| 4 | - | - | - | - | 1 | 1 |
| 5 | - | - | - | - | - | 1 |

• Logic:

  • If there is only one character (diagonal), the max len is 1.
  • In sequence i..j
    • if x[i] =! x[j], i search for the longest palindrome in i+1..j and i,..,j-1
    • if x[i] == x[j], I have two new characters + the max palindrome without them (i+1..j-1)

• d[i, j] is the longest palindrome subsequence from char i to j.

• i == j -> only one char -> 1

• We proceed with increasing sequences

• if v[i] == v[j] the len starts from 2 counting the two characters + the longest from the remaining subsequences

• for l = 2,

  • if v[i] == v[j] => d[i,j] = 2 + d(i+1, j-1) because if i == j, we need to consider the subsequence i+1, j-1
  • if v[i] != v[j] => d[i,j] = max(d(i+1, j), d(i,j-1))

• we proceed for l=3, 4 and so on

// s[0..n-1]
LPS(s)
    n = s.len
    let d[0..n-1, 0..n-1] be a table
    
    for i = 0 to n - 1
        // diagonal
        d[i, i] = 1
    
    for l = 2 to n
        for i = 0 to n-l
            j = i+l-1
            if(s[i] == s[j])
                d[i,j] = 2 + d[i+1, j-1]
            else 
                d[i,j] = max (d[i+1, j], d[i, j-1])

    print("Len of longest palindrome is: " + d[0, n-1])

    // To print the result
    j = n-1
    i = 0

    sel = []
    while (j >= 0 && i < n)
        if(d[i,j] == 0)
            break
        if(d[i,j] == 2 + d[i+1, j-1])
            sel.push(s[i])
            i++
            j--
        else if d[i+1,j] > d[i,j-1]
            i++
        else 
            j--

    # Print first half of the palindrome inorder
    for el in sel:
        print(el, end='')

    # Print the second half of the palindrome in reverse order
    for el in reversed(sel):
        print(el, end='')