I need your help given string A, B. How to find longest subsequence of A that doesn't include B as substring ?

Rating changes for the last round are temporarily rolled back. They will be returned soon.
×

# | User | Rating |
---|---|---|

1 | tourist | 3557 |

2 | Radewoosh | 3468 |

3 | Um_nik | 3429 |

4 | Petr | 3354 |

5 | Benq | 3286 |

6 | mnbvmar | 3280 |

7 | LHiC | 3276 |

8 | wxhtxdy | 3258 |

9 | ecnerwala | 3214 |

10 | yutaka1999 | 3190 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | tourist | 173 |

4 | Vovuh | 167 |

5 | antontrygubO_o | 166 |

6 | PikMike | 164 |

7 | rng_58 | 160 |

8 | majk | 157 |

9 | Um_nik | 155 |

9 | 300iq | 155 |

I need your help given string A, B. How to find longest subsequence of A that doesn't include B as substring ?

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/23/2019 15:16:39 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Same problem https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/

no not the same, please spend some time understanding before answering ...

What are the constraints of the problem?

If you're okay with an n*m solution (where n is the length of A and m is the length of B) then you can have a dp where dp[pos][matched] is a state where you're at some character in A and you've matched "matched" characters of B so far. So when processing a character of A (we'll call it c), there are two situations:

c is equal to the next character in B (B[matched]) and we go to state dp[pos+1][matched+1] or it doesn't match the next character and we go to state dp[pos+1][biggestMatchedPrefix] (see despotovski01's comment) and add 1 to the returned value (since we're increasing the subsequence size by 1). And of course if "matched" is ever equal to the length of B, then this is invalid since we've matched all of B (thus it's a substring of this subsequence)

Or we choose to not take that character and go to state dp[pos+1][matched] and add 0 because we aren't increasing the subsequence size.

If you're looking for a faster solution, I can't really think of one at the moment.

You've made a little mistake, when c doesn't match the next character, we don't necessarily go to 0 matched characters, but to the longest prefix of B that is also the suffix of B[matched] + c. Think like the KMP failure function.

Right I thought I was forgetting something. I think this is actually just very similar to this problem. Thanks for the correction!

this problem statement want to find LCS between A and B that doesn't include C as substring.

i want to make sure .. is it the same as to find

D=LCSbetweenAandB. and then find longest subsequence ofDthat doesn't includeCThat's actually not the case. Consider this test case:

A = viviviaba

B = abavivivi

C = vi

D = vivivi

But the longest subsequence of D that doesn't contain C is 2 ("iv"). But if you instead took the subequence "aba" from A and B, you could get an answer of 3.

now the idea is very clear, thanks a lot Ahmad :)

thanks a lot :)

This problem can be solved in

O(|A| * |B|) complexity. The main idea of the solution includes dynamic programming.We have two parameters in our dp states. First one is obviously the position of string

Awe are currently at, the second one is the length of prefix of stringBwhich has been matched with the current subsequence. Let's denote these parameters asXandYrespectively.Now, at position

Xwe can either include this in our subsequence or skip it. If we skip it, our next call will bedp(X+ 1,Y).Now come to the inclusion part. There are two cases.

First Case:If our character at positionXof stringAmatches with the character at positionYof stringB, then our call will be 1 +dp(X+ 1,Y+ 1). Basically we increment each parameters by one as it matched.Second Case:If our character at those positions do not match, wecan notsimply calldp(X+ 1, 0). Because there is a possibility that some suffix of our subsequence matches with the prefix of stringB. Check this part in following code and try to understand.The

Farray gives us the length of the prefix which is also a suffix at that position. KMP was used to do this inO(N).thanks a lot :)

can you build a bottom-up dp for this problem ?