# 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 non-overlapping 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 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 **F _{i}** means the number of sub-sequences of first

**i**elements which have value 1 and

**A**is selected.

_{i}how to calculate **F _{i}**? by definition

**A**is the last element of all sub-sequences counted in

_{i}**F**so where is the second-last element? it could be anywhere that have distance from i at least

_{i}**M**so

**F**, we added 1 because the sub-sequence that consist of only

_{i}= segma k from 1 to i-M (F_{k}) + 1**A**(so there’s no second last element) should be counted. note that if

_{i}**A**is 0 then

_{i}**F**should be 0 because we only select elements of value 1.

_{i}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 SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.