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/

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;
}

I’m a software engineer with a strong interest in algorithms. I love solving puzzles and love the aha moment of arriving at a solution after hours of struggle.

More from Sweta Barman

I’m a software engineer with a strong interest in algorithms. I love solving puzzles and love the aha moment of arriving at a solution after hours of struggle.