A substring of some character string is a contiguous sequenc

A substring of some character string is a contiguous sequence of characters in that string (which is different than a subsequence, of course). Suppose you are gievn two character strings, X and Y, with respective lengths n and m. Describe an efficient algorithm for finding a longest common substring of X and Y.

Solution

Hi, Please find my algorithm.

Please let me know in case of any issue.

Dynamic Programming can be used to find the longest common substring in O(m*n) time. The idea is to find length of the longest common suffix for all substrings of both strings and store these lengths in a table.

The longest common suffix has following optimal substructure property
LCSuff(X, Y, m, n) = LCSuff(X, Y, m-1, n-1) + 1 if X[m-1] = Y[n-1]
0 Otherwise (if X[m-1] != Y[n-1])

The maximum length Longest Common Suffix is the longest common substring.
LCSubStr(X, Y, m, n) = Max(LCSuff(X, Y, i, j)) where 1 <= i <= m
and 1 <= j <= n

/* Returns length of longest common substring of X[0..m-1]
and Y[0..n-1] */
int LCSubStr(char *X, char *Y, int m, int n)
{
// Create a table to store lengths of longest common suffixes of
// substrings. Notethat LCSuff[i][j] contains length of longest
// common suffix of X[0..i-1] and Y[0..j-1]. The first row and
// first column entries have no logical meaning, they are used only
// for simplicity of program
int LCSuff[m+1][n+1];
int result = 0; // To store length of the longest common substring

/* Following steps build LCSuff[m+1][n+1] in bottom up fashion. */
for (int i=0; i<=m; i++)
{
for (int j=0; j<=n; j++)
{
if (i == 0 || j == 0)
LCSuff[i][j] = 0;

else if (X[i-1] == Y[j-1])
{
LCSuff[i][j] = LCSuff[i-1][j-1] + 1;
result = max(result, LCSuff[i][j]);
}
else LCSuff[i][j] = 0;
}
}
return result;
}

Time Complexity: O(m*n)
Auxiliary Space: O(m*n)