Question

Can I please get help with this? will upvote upon completion.

Problem 2. The longest common substring problem is to find the longest string that is a substring of two strings. The longest common substring of the strings "ABABC", and "ABCBA" is string "ABC" of length 3. A substrings of strings is a series of consecutive letters of s. For example, "ABA” is a substring of “ABABC", but "ABAC" is not a substring of "ABABC". Design an algorithm such that given two strings as input, it finds a longest substring of the two input strings of length m and n, respectively. Hint: You may use dynamic programming method. It needs a recursion, and time analysis to show how the time depends on the two parameters m and n.

Answer 1

Dynamic Programming Approach

Let the first string be s1 and second be s2.Suppose we are at DP state when the length of s1 is i and length of s2 is j, the result of which is stored in dp[i][j]. So, it means:

dp[i][j] = length of the longest substring in first i characters of S1 and first j characters of S2

Now if s1[i-1] == s2[j-1], then dp[i][j] = 1 + dp[i-1][j-1], that is result of current row in matrix dp[][] depends on values from previous row. Hence the required length of longest common substring can be obtained by maintaining values of two consecutive rows only, thereby reducing space requirements to O(2 * n).

dp[i][j] = 1 + dp[i-1][j-1]   if s1[i-1] == s2[j-1]

To print the longest common substring, we use variable end. When dp[i][j] is calculated, it is compared with res where res is the maximum length of the common substring.

If res is less than dp[i][j], then end is updated to i-1 to show that longest common substring ends at index i-1 in s1 and res is updated to dp[i][j]. The longest common substring then is from index end – res + 1 to index end in s1.

For instance,if we consider string doll as str1 and another string dog as str2 and loop through all characters of str1,position denoted by i, and str2,position denoted by j, to build the table dp[][].We consider the variable curr to state the current row which toggles its value to 0 and 1 at the end of every outer iteration.When i=0 we all the values of dp[][] corresponding to the first row is set 0.When i=1 and str1[i-1]!=str2[j-1], dp[curr][j] = 0.When str1[i-1] = str2[j-1] = 'd' (at j=1) , dp[cur][j] = dp[1][1] = dp[1-curr][j-1] + 1 = 0+1 =1. We store the maximum length of longest common substring (maximum value of dp[cur][j]) as res and the ending index of the substring as end. Here res=1 and end=0.

When i=2 and j=2, curr=0, str1[i-1] = 'o' and str2[j-1] = 'o'.Since str1[i-1] = str2[j-1] therefore dp[curr][j] = dp[1-curr][j-1] + 1 = dp[1][1] + 1 = 1 + 1 = 2.
Since res = 1 which is less than dp[curr][j], res = dp[curr][j] = 2 and end = i-1 = 1.

All other positions of dp is less than res.So finally the length of the largest common substring between doll and dog is 2.

To retrieve the substring iterate from position end-res+1 i.e. 1-2+1 = 0 till end i.e. 1 in str1 doll to get do as the largest common substring between dog and doll.

Time Complexity

• Worst case time complexity: O(m*n)
• Average case time complexity: O(m*n)
• Best case time complexity: O(m*n)
• Space complexity: O(2*n)

Since we are using two for loops for both the strings ,therefore the time complexity of finding the longest common substring using dynamic programming approach is O(n * m) where n and m are the lengths of the strings.Since this implemetation involves only two rows and n columns for building dp[][],therefore, the space complexity would be O(2 * n).

Pseudocode of Dynamic Programming approach:

Following is the pseudo code for dynamic programming implementation:-

longest_substring(X, Y, m, n)
  
   dp = [[0 for k in range(n+1)] for l in range(m+1)] 
      
    # To store the length of longest common substring 
    result = 0 
  
    # Following steps to build 
    # dp[m+1][n+1] in bottom up fashion 
    for i in range(m + 1): 
        for j in range(n + 1): 
            if (i == 0 or j == 0): 
                dp[i][j] = 0
            elif (X[i-1] == Y[j-1]): 
                dp[i][j] = dp[i-1][j-1] + 1
                if (result < dp[i][j]) 
                { 
                    result = dp[i][j]; 
                    r = i; 
                    c = j; 
                } 
            else: 
                dp[i][j] = 0
    while (dp[r][c] != 0)
    { 
        ans[--result] = X[r - 1]; 
        r--; 
        c--; 
    } 
    return ans