Bliss8's blog

By Bliss8, 15 months ago, In English,

Recently there was a problem DIV2 A to count subsequences 'QAQ' in given string

There is O(N) solution for that problem: count how many 'Q' we have on a prefix[i], and then for each 'A' res+=prefix[i]*(qTotal - prefix[i]). (multiply number of 'Q's to the left and right from 'A')

But what if we had to count 'QAQAQ' or any other sequence? I would like to get some insights on general solution of the problem.

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

»
15 months ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it

Let's suppose in the general problem, we have 2 strings S and T, and we need to count the amount of subsequences in S that are equal to T. Let's denote |S| = n, |T| = k (|a| stands for string a's length).

We can maintain an array dp[k], where each cell dp[i] denotes the amount of subsequences we found until now, that are equal to the first i characters of T (we'll use 1-indexing just to ease on understanding). initially the array dp is set to all 0.

We process S's characters from left to right, let's denote the currect one as C. for each location X so that T[X] = C, we do dp[X] = dp[X] + dp[X - 1]. If one of the X's is 1 (the first character), we do dp[1] = dp[1] + 1. Please note, that we should iterate on these X values from big to small, otherwise, we could be doing something like: dp[2] = dp[2] + dp[1], dp[3] = dp[3] + dp[2], dp[4] = dp[4] + dp[3]..., which shouldn't happen while we're checking a single character in S.

Once we're done, the answer will be in dp[k]. The running time is, on worst case, O(nk)

  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    nice solution. thanks

  • »
    »
    15 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thanks. My accepted solution using your approach. :)

    http://codeforces.com/contest/894/submission/32612277

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is a good solution. I'm new to DP and trying to understand how to formulate DP solutions. The solution which Noam posted is not very obvious to me. Is there a theory behind how to approach the category of the problem mentioned above? And is that what Noam has suggested here?