PROBLEM LINK:DIFFICULTY:Easy PREREQUISITES:KMP, dynamice programming PROBLEM:Given two strings S and F, how many ways there are to choose arbitrary number of nonoverlapping substrings of S so that each substring is equal to F. output the answer modulo 10^{9} + 7. EXPLANATION:let's say the length of string S is N, and the length of string F is M. the solution which we are going to describe will consist of two parts, the first part is to calculate an array A which we are going to define below then the second part is make use of that array to calculate the final answer. what is that array A? it's an array of length N such that each element can be either 0 or 1, if the substring of length M which ends at i is equal to string M then A_{i} is equal to 1, otherwise it's equal to 0. how to calculate this array? this is a standard problem known as "string matching problem" which can be done by various algorithms, in particular it can be done in O(N+M) using KMP algorithm. now after we calculate that array the problem is reduced to calculating the number of subsequences of A such that all elements of the subsequence are equal to 1 and no two elements of the subsequence have distance from each other less than M (otherwise those two elements will correspond to overlapping substrings of string S) to calculate the number of subsequences we will use dynamic programming: let F_{i} means the number of subsequences of first i elements which have value 1 and A_{i} is selected. how to calculate F_{i}? by definition A_{i} is the last element of all subsequences counted in F_{i} so where is the secondlast element? it could be anywhere that have distance from i at least M so F_{i} = segma k from 1 to iM (F_{k}) + 1, we added 1 because the subsequence that consist of only A_{i} (so there's no second last element) should be counted. note that if A_{i} is 0 then F_{i} should be 0 because we only select elements of value 1. calculating each value of F takes O(N) steps, and we need to calculate O(N) values, so overall complexity is O(N^{2}), but if we notice that elements inside the sigma are always a prefix of F, then we can use cumulative prefix sums so we can calculate the sigma in O(1) and overall complexity of dynamic programming would be O(N) SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 24 Oct '16, 00:36

@forhadsidhu , consider the following code and then the given explanation
}
answered 20 Nov '16, 14:21

you can refer this solution https://www.codechef.com/viewsolution/12062714 answered 16 Nov '16, 14:31

The dynamic programming part is same as what was used in goodsets problem of ICPC online round. answered 16 Nov '16, 23:09

you can see this solution https://www.codechef.com/submit/complete/12112951 answered 18 Nov '16, 14:08

Can someone please explain the use of the dist array in the solution link,which is shared in one of the above comments?