minimario's blog

Help on Problem 346B
By minimario, history, 9 years ago, In English

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

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice tags.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

UPD:: I was wong.. sorry

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I cannot understand, what you mean, the last k characters don't match? And I still cannot see the transitions...

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

ojneqfnjodmklqefmd,z

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply