Edit distance variant — longest common substring

We take a look at a variant of the Longest common subsequence problem — which is the longest common substring problem.

8–3. The longest common substring (not subsequence) of two strings X and Y is the longest string that appears as a run of consecutive letters in both strings. For example, the longest common substring of photograph and tomography is ograph.

1. Let n=|X| and m=|Y|. Give a Θ(nm) dynamic programming algorithm for longest common substring based on the longest common subsequence/edit distance algorithm.

In order to solve this problem — we need to figure out the recurrence relation

String X = “oabcd”

String Y = “oxbcda”

To evaluate a substring, we need to realize that if two characters in a string are equal, then the preceding characters also need to be added up if we need to evaluate the maximum length of the common substring.

dp[i][j] = 0, if X.charAt(i) != Y.charAt(j)

dp[i][j] = 1 + dp[i-1][j-1], if X.charAt(i) == Y.charAt(j)

Similar problem on leetcode : https://leetcode.com/problems/maximum-length-of-repeated-subarray/

Solution of https://leetcode.com/problems/maximum-length-of-repeated-subarray/:

public int findLength(int[] A, int[] B) {
        int[][] dp = new int[A.length+1][B.length +1];
        int max = 0;
        for(int i = 1; i <= A.length; i++) {
            for(int j = 1; j <= B.length; j++) {
                int A_i = A[i-1];
                int B_j = B[j-1];
                if(A_i == B_j) {
                    dp[i][j] = 1 + dp[i-1][j-1];
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }