×

Easy

# PREREQUISITES:

KMP, dynamice programming

# PROBLEM:

Given two strings S and F, how many ways there are to choose arbitrary number of non-overlapping substrings of S so that each substring is equal to F. output the answer modulo 109 + 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 Ai 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 sub-sequences of A such that all elements of the sub-sequence are equal to 1 and no two elements of the sub-sequence 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 sub-sequences we will use dynamic programming:

let Fi means the number of sub-sequences of first i elements which have value 1 and Ai is selected.

how to calculate Fi? by definition Ai is the last element of all sub-sequences counted in Fi so where is the second-last element? it could be anywhere that have distance from i at least M so Fi = segma k from 1 to i-M (Fk) + 1, we added 1 because the sub-sequence that consist of only Ai (so there's no second last element) should be counted. note that if Ai is 0 then Fi 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(N2), 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 SOLUTION

Can be found here.

# TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

194824
accept rate: 12%

19.7k350498541

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

(17 Nov '16, 01:09)

 7 @forhadsidhu , consider the following code and then the given explanation- ll doit(int pos,int sel,int n){ if(pos==n){ return sel; } if(dp[pos][sel]!=-1) return dp[pos][sel]; ll ans=0; if(mark[pos]){ ans=ans+doit(pos+m,1,n)+doit(pos+1,sel,n); } else ans=ans+doit(pos+1,sel,n); dp[pos][sel]=ans%mod; return ans%mod;  } parameter pos represent the index at where I am at current time ,and sel represent if I have selected atleast one pattern or not. mark[i] represent that if any pattern start from ith position or not. now at every instant you have two cases , Either a pattern starts at this location or not - now if a pattern start at current position , you have two option either select current pattern and go to pos=pos+length_of_pattern , or do not select the pattern and go to position pos=pos+1 , if you select the pattern make the value of sel=1 for further calls. if pattern does not start at this position , you have only one option go to pos=pos+1 when you reach at the end if sel=1 return 1 because this is a valid configuration or return 0 answered 20 Nov '16, 14:21 4★anshal21 606●8 accept rate: 7%
 0 solutions link not working answered 16 Nov '16, 14:09 1.2k●11 accept rate: 19%
 0 you can refer this solution https://www.codechef.com/viewsolution/12062714 answered 16 Nov '16, 14:31 4★shukrant 121●4 accept rate: 22%
 0 The dynamic programming part is same as what was used in goodsets problem of ICPC online round. answered 16 Nov '16, 23:09 1.1k●2●11 accept rate: 10%
 0 you can see this solution https://www.codechef.com/submit/complete/12112951 answered 18 Nov '16, 14:08 3★wa_6907 1 accept rate: 0%
 0 anyone plz explain the dp part of the solution! answered 20 Nov '16, 10:43 1 accept rate: 0%
 0 answered 21 Nov '16, 20:32 2★mypc107 1 accept rate: 0%
 0 what type of dp approach is this ? answered 22 Nov '16, 00:12 1 accept rate: 0%
 0 nyc problem :) answered 23 Nov '16, 08:53 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,477
×3,704
×2,085
×150
×66
×26

question asked: 24 Oct '16, 00:36

question was seen: 4,906 times

last updated: 23 Nov '16, 08:53