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

Example:
Input:

S1 :“c r e e k”

S2: “g e e k s”

Output:

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:

O(m*n)

Go to top