# Word Collection - EDITORIAL:

Practice

Contest

Author and Editorialist: kishen1912000

Medium

# PROBLEM:

You are given two strings N and W. You need to find the total number of ways to cut off non-zero number of W's from N. Note that when one occurrence of W is cut-off, if there existed an overlapping occurrence originally, then it cannot be cut-off anymore (as part of it is no more present). For example, in ababa, you can cut-off only one occurrence of aba at a time, as they are overlapping. Return the answer modulo 10^9+7.

# QUICK EXPLANATION:

Use an efficient pattern matching algorithm (like KMP, etc) to find all the occurrences of W in N. Store this info as a bit array, where a 1 at index i denotes that an occurrence of W ended at index i. Next, using dynamic programming and prefix sums, find the number of ways of picking 1's such that the picked 1's are at least |W| distance apart.

# EXPLANATION:

First of all, let us convince ourselves that we need to obtain all the occurrences of W in N. Without this info we cannot proceed to solve this problem. For this purpose, we can use any efficient pattern matching algorithm like Knuth-Morris-Pratt Algorithm (KMP), Z-Algorithm, etc. I will not discuss these algorithms here, but you can find out more about them here.

Let us store the information from the above algorithm in an array A where the value at index i is 1 if an occurrence of W in N ends at index i. Otherwise, the value is 0.

For example, Let N = ababa and W = aba. Then, A = [0,0,1,0,1].

Now, essentially we have reduced our problem to the following problem, what are the total number of ways to pick non-zero number of 1's from A such that the picked 1's are mutually at least |W| distance apart.

This problem can be solved using Dynamic Programming.

Let dp[i] denote the number of ways of picking non-zero number of 1's in the array A[1..i] such that the chosen 1's are mutually at least |W| distance away, and the 1 at A[i] is picked. If A[i]=0, then dp[i]=0.

Also, let prefix[i] = \sum_{j=1}^{i}dp[j]. prefix[i] essentially denotes the number of ways to pick non-zero number of 1's in the array A[1..i] such that the chosen 1's are mutually at least |W| distance apart.

When we are processing index i, if A[i] = 1, that means we pick this 1. So, now we need to find the total number of ways to pick non-zero 1's in the array A[1..i-|W|]. That is nothing but prefix[i-|W|]. Therefore, we get
dp[i] = 1+prefix[i-|W|]

Also, update prefix[i] = prefix[i-1]+dp[i]

The final answer will be prefix[n].

Also, as the values can go huge, appropriate modular arithmetic is to be applied at places.

Further, the space can be improved if we use dp[i] to directly store the prefix[i] value, as dp[i] only depends on prefix[i] value.

# Time Complexity:

Time taken for pre-processing (finding A) = \mathcal{O}(|N|+|W|)
Time taken to compute dp = \mathcal{O}(|N|)

Running time: \mathcal{O}(|N|+|W|)

# SOLUTIONS:

Setter's Solution
M = 10**9+7
def lps_compute(s):
n = len(s)
lps = *n
curr = 0
lps = 0
i = 1
while i < n:
if s[i]== s[curr]:
curr += 1
lps[i] = curr
i += 1
else:
if curr != 0:
curr = lps[curr-1]
else:
lps[i] = 0
i += 1
return lps

def kmp(s1,s2):
n,m = len(s1),len(s2)
lps = lps_compute(s2)
ans = *n
i,j = 0,0
while i < n:
if s1[i] == s2[j]:
i += 1
j += 1
else:
if j==0:
i+=1
else:
j = lps[j-1]
if j == m:
ans[i-1] = 1
j = lps[j-1]
return ans

for _ in range(int(input())):
s1 = input().strip()
s2 = input().strip()
n,m = len(s1),len(s2)
arr = kmp(s1,s2)
dp = *n
if arr == 1:
dp = 1
for i in range(1,n):
if arr[i]==1:
if i==m-1:
dp[i] = 1
else:
dp[i] = (1 + dp[i-m])%M
dp[i] = (dp[i-1]+dp[i])%M
print(dp[-1])

2 Likes