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.

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 stringa's length).We can maintain an array

dp[k], where each celldp[i] denotes the amount of subsequences we found until now, that are equal to the firsticharacters ofT(we'll use 1-indexing just to ease on understanding). initially the arraydpis set to all 0.We process

S's characters from left to right, let's denote the currect one asC. for each locationXso thatT[X] =C, we dodp[X] =dp[X] +dp[X- 1]. If one of the X's is 1 (the first character), we dodp[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 asinglecharacter inS.Once we're done, the answer will be in

dp[k]. The running time is, on worst case,O(nk)nice solution. thanks

Thanks. My accepted solution using your approach. :)

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

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?