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