'Lucky Common Subsequence' problem from codeforces

#1

I am not able to understand the editorial.
Problem link - https://codeforces.com/contest/347/problem/D

#2

@yuvi2701 hey this problem is classical longest common string problem(LCS), dp algorithm classical string matching problem, kmp algorithm.

solution: First,for LCS, dp[n][m]= dp[n-1][m-1] ;if two char match max(dp[n-1][m],dp[n][m-1]) ;if two char not match then, there is virus dp[n][m][k]= dp[n-1][m-1][k-1] ;if all three char match dp[n-1][m-1][fk] ;if only two char match, fk start over max(dp[n-1][m][k],dp[n][m-1][k]); dp[n][m][k] means the virus after k is all matched, so if k <0 then all virus matched, which is invalid.

for the equation dp[n][m][k]=dp[n-1][m-1][fk] ;if only two char match, fk start over just two char match, so the virus must has to start from the beginning, but may not real beginning. strA: BCBC strB: BCBC virus:ACBC when matching from the right to left, and meets (B,B,A), although matching failed at A, but there is still has a matching string of ‘BC’, we just not need to start from the real begining. Where to find the place for rematching?

Finally, we came to kmp. 0…k…j…n nxt[j]=k: the substring from [0,k] is the same as substring [j-k,j] for one j, k<j and k is the max.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.