Longest Common Substring

Given two strings s1 and s2. Find out the longest common substring.
Lets solve this problem using Dynamic Programming.
We assume a 2D matrix such that m[i][j] is the maximum length of LCS in substring s1[0..i] and s2[0..j].

Recursive formula to get the length of LCS:

m[i][j]  = 0 if(i==0, j==0)
         = m[i-1][j-1] + 1 if(s1[i] == s2[j])
         = max( m[i][j-1], m[i-1][j] ) if(s1[i] != s2[j])

Using this recursive formula m[s1.size()][s2.size()] will give the maximum length of the common substring.

Code to get the LCS matrix:

 int **getLCSMatrix(string s1, string s2) {
  int r = s1.size() + 1, c = s2.size() + 1;
  int **m = (int**) malloc(r * sizeof(int *));
  for (int i = 0; i < c; i++)
   m[i] = (int *) malloc(c * sizeof(int));

  for (int i = 0; i < r; i++)
   m[i][0] = 0;

  for (int i = 0; i < c; i++)
   m[0][i] = 0;

  for (int i = 1; i < r; i++) {
   for (int j = 1; j < c; j++) {
    if (s1[i - 1] == s2[j - 1]) {
     m[i][j] = m[i - 1][j - 1] + 1;
    } else {
     m[i][j] = max(m[i - 1][j], m[i][j - 1]);
    }
   }
  }
  return m;
 }

Now, we can easily use this matrix to get the maximum length.
Output:

LCS length: 3

Reading out an LCS:

The following code backtracks the choices taken when computing the LCS matrix. If the last characters in the prefixes are equal, they must be in an LCS. If not, check what gave the largest LCS of keeping s1[i] and s2[j], and make the same choice. Just choose one if they were equally long. Call the function with i=s1.size() and j=s2.size().

 string getLCS(int **m, int i, int j, string s1, string s2) {
  if (i == 0 || j == 0)
   return "";
  if (s1[i - 1] == s2[j - 1])
   return getLCS(m, i - 1, j - 1, s1, s2) + s1[i - 1];
  else if (m[i - 1][j] < m[i][j - 1])
   return getLCS(m, i, j - 1, s1, s2);
  else
   return getLCS(m, i - 1, j, s1, s2);
 }

Reading out all the LCS:

 set getAllLCS(int **m, int i, int j, string s1, string s2,
   string s) {
  set v;
  if (i == 0 || j == 0) {
   v.insert(s);
   return v;
  }

  if (s1[i - 1] == s2[j - 1]) {
   set v1 = getAllLCS(m, i - 1, j - 1, s1, s2, s1[i - 1] + s);
   v.insert(v1.begin(), v1.end());
  } else if (m[i - 1][j] == m[i][j - 1]) {
   set v1 = getAllLCS(m, i - 1, j, s1, s2, s);
   set v2 = getAllLCS(m, i, j - 1, s1, s2, s);
   v.insert(v1.begin(), v1.end());
   v.insert(v2.begin(), v2.end());
  } else if (m[i - 1][j] < m[i][j - 1]) {
   set v1 = getAllLCS(m, i, j - 1, s1, s2, s);
   v.insert(v1.begin(), v1.end());
  } else {
   set v1 = getAllLCS(m, i - 1, j, s1, s2, s);
   v.insert(v1.begin(), v1.end());
  }
  return v;
 }

You can find the complete source code on my github page: Here

Maximum Sub Matrix Sum

Given a matrix of both +ve and -ve numbers, find out the maximum sum sub matrix. First of all we will calculate the sum matrix where s[i][j] = sum of all the elements from [0,0] to [i,j]

int s[ROW][COL];
 void computeSumMatrix(int a[][COL], int r, int c) {
  for (int i = 0; i < r; i++)
   if (i == 0)
    s[i][0] = a[i][0];
   else
    s[i][0] = s[i - 1][0] + a[i][0];

  for (int j = 0; j < c; j++)
   if (j == 0)
    s[0][j] = a[0][j];
   else
    s[0][j] = s[0][j - 1] + a[0][j];

  for (int i = 1; i < r; i++) {
   for (int j = 1; j < c; j++) {
    s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
   }
  }
 }

Now we will write a method to get the sum of a sub matrix given upper-left (r1,c1) indexes and lower-bottom (r2,c2) indexes

int getSubmatSum(int r1, int c1, int r2, int c2) {
  if (r1 == 0 && c1 == 0)
   return s[r2][c2];
  if (r1 == 0)
   return s[r2][c2] - s[r2][c1 - 1];
  if (c1 == 0)
   return s[r2][c2] - s[r1 - 1][c2];
  return s[r2][c2] - s[r1 - 1][c2] - s[r2][c1 - 1] + s[r1 - 1][c1 - 1];
 }

Using both these methods, we can iterate through all the possible sub matrices and get their sum in O(1). To iterate though all the possible sub-matrices would take O(n^4).

int getMaxSubmatSum(int a[][COL], int r, int c) {
  int maxsum = 0;
  for (int r1 = 0; r1 < r; r1++) {
   for (int c1 = 0; c1 < c; c1++) {
    for (int r2 = r1; r2 < r; r2++) {
     for (int c2 = c1; c2 < c; c2++) {
      int sum = getSubmatSum(r1, c1, r2, c2);
      maxsum = max(sum, maxsum);
     }
    }
   }
  }
  return maxsum;
 }

Now, we are going to optimize this solution to O(n^3). The trick is to apply Kadane's algorithm on a 2D matrix. We will consider all the possible 2D matrices which are starting from 0th column and treat them as 1D arrays.

int getMaxSubmatSum2(int a[][COL], int r, int c) {
  int globalmax = 0;

  for (int i = 0; i < r; i++)
   for (int j = i; j < r; j++) {
    int localmax = 0;
    for (int k = 0; k < c; k++) {
     localmax = max(localmax + getSubmatSum(i, k, j, k), 0);
     globalmax = max(localmax, globalmax);
    }
   }

  return globalmax;
 }

Test Cases
Given Matrix:
1 1 1
1 1 1
1 1 1
Maximum Sum : 9 (because all numbers are positive, we will output complete matrix)

Given Matrix:
-1 -2 -3 -4
-5 -6 -7 -8
-9 -10 -11 -12
-13 -14 -15 -16
Maximum Sum : 0 ( we take nothing, as all numbers are negative)

Given Matrix:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

Maximum Sum: 15
Output Matrix :
9 2
-4 1
-1 8

You can find the full source code of both these algorithms on my github page: Here