Longest Common subsequence

general
,
1

Supposing that we have a string not in the classic form but in a form like that
A1B1C1D2E1G1F1
A1B1C1D2F1P1X1

where the numbers are the frequencies of chars.

How can i work the longest common subsequence? I have worked with arrays of struct but i find some difficulty. Can someone provide code for the LCS part working also with frequencies?

2

What’s the issue in converting this encoded string back to its original form and then applying LCS algo?

3

That would be really slower wouldn’t be?

4

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1346

3 Likes
5

Assuming that you are using a classic implementation for LCS, (I’m using Wikipedia as a reference), this is what you could do:

  1. Store the character and frequency as a key:value pair, say in a struct. Hence each string could be represented as a linked list of such structs.
  2. Make the traditional 2D array used in LCS.
  3. When there is a match at a particular cell, instead of appending only the character, append a struct that has the character and the minimum of the two frequencies. (Each cell could be a linked list as well).

Small example: Consider the two strings:
A1B2C1D2
A2B1C3E3

alt text

Legend (in terms of steps followed): Orange -> Blue -> Pink -> Red -> Black

  1. Whenever there is no match, simply take the longer string from the top and left cells.
  2. If there is a match, append the longest possible match to the top left cell value and store in current cell.

Reference: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

6

You can use the same DP as for LCS of characters (dp[i][j] is the LCS of the first i characters of the first string and the first j characters of the second one), but on arrays of different objects than characters - those “repeated character” objects in this case.

Where you had dp[i][j] =max(dp[i][j],dp[i-1][j-1]+1), you should replace that 1 by LCS(object i, object j), which is 0 if they have different repeated characters and minimum of their lengths otherwise.