COLWORD - Editorial

editorial
, , , , ,
1

Word Collection - EDITORIAL:

Practice

Contest

Author and Editorialist: kishen1912000

DIFFICULTY:

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 = [0]*n
    curr = 0
    lps[0] = 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 = [0]*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 = [0]*n
    if arr[0] == 1:
        dp[0] = 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