Need help with a problem involving lcs with k Mismatch

Правка en1, от __Noice__, 2023-03-04 13:09:52

In this problem, we'll use the term "longest common substring" loosely. It refers to substrings differing at some number or fewer characters when compared index by index. For example, 'abc' and 'adc' differ in one position, 'aab' and 'aba' differ in two.

Given two strings and an integer k , determine the length of the longest common substrings of the two strings that differ in no more than k positions.

The link to the problem is : Problem Link

I am not able to understand the solution. It would be helpful if anyone can provide a good explanation. I am able to write the brute force solution but it gives TLE.

Теги dp, string, c++, lcs

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский __Noice__ 2023-03-04 13:09:52 740 Initial revision (published)