I__Love__TANIA's blog

Need help to solve "Toph — Very Dirty String"
By I__Love__TANIA, history, 6 years ago, In English

Need some help to solve Very Dirty String problem.

Short Description:

Given three strings A, B and C. Find the longest common sub-sequence of A and B, which have C at-least once as a substring in it.

Input: There will be T test cases. For each test there will be three lines describing string A, B, and C.

Constraints: 1 ≤ T ≤ 100 1 ≤ |A|, |B|, |C| ≤ 100

My approach: I tried it using normal recursive LCS with extra another state pointing the index of string C i'm trying to match.

here is my code.

Sorry for my bad English.

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 5   Vote: I like it +6 Vote: I do not like it

Compute the LCS two times, once for A and B and once for reverse(A) and reverse(B).

Let n = A.size() and m = B.size() , we should have:

  • LCS_1[ i ][ j ] = length of the longest common subsequence of A[1..i] and B[1..j].
  • LCS_2[ i ][ j ] = length of the longest common subsequence of A[i..n] and B[j..m].

Now, we know that C must be present as a substring at least once in the subsequence we're looking for.For every 1 <= i <= n find out the minimum index j such that C is a subsequence of A[i..j] and do the same for B.And store these (i,j) for A and B.We will have at most n pairs for A and at most m pairs for B.

For each pair p1=(i1,j1) that belongs to A go through all the pairs p2=(i2,j2) of B.Now we have C present in the two strings A[i1..j1] and B[i2..j2] (as a subsequence) so we need to maximize the LCS of A[1..i1-1] with B[1..i2-1] and A[j1+1..n] with B[j2+1..m].

For any pair of pairs (p1,p2) the answer will be:

LCS_1[i1-1][i2-1] + C.size() + LCS_2[j1+1][j2+1]

The final complexity will be O(len(A)*len(B) + len(A)*len(C) + len(B)*len(C)) for each test case.

→ Reply