Hello, Codeforces:
I worked on problem 346B for a long time, and I could not come up with solution. Even when I read editorial and comments, the solution is still unclear to me. I know, it is KMP + DP, but I cannot see what KMP should be used on, DP transitions, etc. I know in the dp[i][j][k], i and j represent indices in str1 and str2, and k represents the longest match of the current subsequence and virus, but I cannot really get anything else.
I have worked for a few hours, but I don't have really much progress, and editorial/comments doesn't really help. So if anyone could give a clear explanation of this problem, it would be great and I would much appreciate it.
Thanks,
minimario
Nice tags.
UPD:: I was wong.. sorry
I cannot understand, what you mean, the last k characters don't match? And I still cannot see the transitions...
Are you sure about your solution. Did you write the code? Because you are looking for last k chars. But there can be a virus in another place. Like that:
ABABA
ABABA
AB
dp[3][3][1]="AB" (its last 1 char doesn't match with v[1] but its the same of virus )
dp[4][4][2]=dp[3][3][1]+1 = "ABB"
dp[5][5][3]=dp[4][4][2]+1 = "ABBA" (last 3 chars are different from virus)
ojneqfnjodmklqefmd,z
Consider we are at state (i, j, k). If str1[i] = = str2[j] and we choose to take this character, then we reach state (i + 1, j + 1, k'), where k' is the new length of match in str3. Consider the string str3[0]...str3[k - 1], str1[i]. If str1[i] = = str3[k], then k' = k + 1, otherwise k' is the maximum length of prefix which is also a suffix. This can be found by using KMP.