Highest Value Longest Common Subsequence (HVLCS)

Student

• Name: Anthony Cao
• UFID: 22929899

---

How to Run

python src/main.py data/test1.in

python src/main.py data/test(#).in

---

Input Format

K
x1 v1
x2 v2
... xK vK
A
B

K = number of characters in the alphabet
xi vi = character xi and its assigned value vi
A = first string
B = second string

---

Output Format

First line: the maximum value of a common subsequence of A and B
Second line: one subsequence that achieves this value (if multiple exist, any is valid)

---

Example

Run:

python src/main.py data/example.in

Input (data/example.in):

3
a 2
b 4
c 5
aacb
caab

Output:

9
cb

Explanation: The subsequence cb has a total value 5 + 4 = 9, which is the highest possible.

---

Question 1

Question 2

Let:

A = a1 a2 ... am, B = b1 b2 ... bn
v(c) = value of character c H[i][j] = maximum value of a common subsequence of the first i characters of A and the first j characters of B
Recurrence:
H[i][j] = 0 if i == 0 or j == 0
H[i][j] = H[i-1][j-1] + v(A[i]) if A[i] == B[j]
H[i][j] = max(H[i-1][j], H[i][j-1]) if A[i] != B[j]
Explanation:
Matching characters: Include A[i] in the subsequence and add its value to the previous optimal solution.
Non-matching characters: Take the maximum of excluding A[i] or B[j].
Empty prefixes: Maximum value is 0 if either string is empty.

Question 3

Pseudocode:

function HVLCS(A, B, value):    
    m = len(A)  
    n = len(B)  
    create table H of size (m+1)x(n+1) initialized to 0 

    for i = 1 to m:
        for j = 1 to n:
            if A[i-1] == B[j-1]:
                H[i][j] = H[i-1][j-1] + value[A[i-1]]
            else:
                H[i][j] = max(H[i-1][j], H[i][j-1])

    i, j = m, n
    subseq = []
    while i > 0 and j > 0:
        if A[i-1] == B[j-1] and H[i][j] == H[i-1][j-1] + value[A[i-1]]:
            prepend A[i-1] to subseq
            i -= 1
            j -= 1
        elif H[i-1][j] >= H[i][j-1]:
            i -= 1
        else:
            j -= 1

    return H[m][n], join(subseq)

Runtime: O(m * n)