Description: We have to find the longest common substring between 2 strings S1 (of length ‘m’) and S2 (of length ‘n’).


S1 :“c r e e k”

S2: “g e e k s”


Longest Common Substring: “eek”

Algorithm and Implementation:

We’ll solve the problem using dynamic programming.

Lets first define :

LCS (j,k): Length of the Largest common suffix for the first  ‘j’ elements of S1 and first ‘k’ elements of S2.                                                                                                

LCS (j,k )=={  

                                                LCS (j-1,k-1)+1,  if S1[j-1]==S2[k-1]

                                                0                        , otherwise


Length of longest common substring:         max of LCS (j, k)

                                                           for j=1->m and k=1->n

To solve the problem using Dynamic Programming, we create a 2-D matrix containing values of LCS(j,k) in the jth row and kth column.


C implementation

/*To store length of the longest common substring*/
int length= 0; 
for(int i=0; i<=m; i++)
 for(int j=0; j<=n; j++)
if(i == 0 || j == 0)
LCS[i][j] = 0;
elseif(S1[i-1] == S2[j-1])
 LCS[i][j] = LCS[i-1][j-1] + 1;
 /*’max’ find the maximum among 2 values*/
 length = max(length, LCS[i][j]);
 else LCS[i][j] = 0;
 /*return length of longest substring*/
 return length; 
Time Complexity:


Go to top