http://codeforces.net/contest/346/problem/B 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.