Find Two Substrings with Longest Distance from Two Strings

Problem: Given two strings s1 and s2, s1' and s2' are two substrings of s1 and s2, respectively. Find the s1' and s2' with longest distance. Distance is defined as \sum_i| s1' [i] -s2' [i]|.

Solution: Obviously,  s1' and s2' should be of equal length. Here give a O(n*m) algorithm where n and m are the length of  s1 and s2,  respectively.

• Calculate c[i][j] = |s1[i]-s2[j]|, then we have a matrix.
• Swipe the matrix with a diagonal line. For example, s1 = "35645",  s2 ="2475", we have matrix c as follow:
  1 1 4 2
  3 1 2 0
  4 2 1 1
  2 0 3 1
  3 1 2 0
• First we scan "2", then "4 0",  then "1 2 1". You calculate the sum of the numbers in the line. Later you will find the maximum is "3 2 3 0" or "3 2 3", which stands for the distance of "5645" and "2475".