# 1. Introduction

The Longest Common Substring (LCS) problem is to find the longest string (or strings) that is a substring (or are substrings) of two strings. This is different from the Longest Common Subsequence problem, where the sequence of characters in the subsequence need not be consecutive in the given strings. Dynamic Programming is a powerful technique used to solve this problem.

# 2. Program Steps

1. Create a function *LCSubstring* that takes two strings as its parameters.

2. Create a 2D array *dp* to store lengths of the longest common suffixes of substrings.

3. Initialize the length of the longest common substring as 0.

4. Using nested loops, fill in the *dp* table.

5. If there is a match between characters of the two strings, calculate the length of the current common substring.

6. Update the length of the longest common substring whenever a larger common substring is found.

7. Return the length of the longest common substring.

8. Within the *main* method, use two sample strings and display their longest common substring length.

# 3. Code Program

```
public class LongestCommonSubstring {
public static int LCSubstring(String X, String Y) {
int m = X.length();
int n = Y.length();
// Create a table to store lengths of longest common suffixes of substrings
int[][] dp = new int[m + 1][n + 1];
int result = 0;
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else if (X.charAt(i - 1) == Y.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
result = Math.max(result, dp[i][j]);
} else {
dp[i][j] = 0;
}
}
}
return result;
}
public static void main(String[] args) {
String X = "ABCDEF";
String Y = "ZBCDMF";
System.out.println("Length of Longest Common Substring: " + LCSubstring(X, Y));
}
}
```

### Output:

Length of Longest Common Substring: 2

# 4. Step By Step Explanation

1. The function *LCSubstring* is designed to find the longest common substring between two input strings *X* and *Y*.

2. We maintain a 2D array *dp* which helps in storing the longest common suffix for substrings of *X* and *Y*.

3. For every character in *X* and *Y*, if there's a match, the common substring's length is one more than the length of the common substring of the previous characters. This is represented by *dp[i][j] = dp[i – 1][j – 1] + 1*.

4. *result* keeps track of the maximum length encountered so far. We update it whenever we find a larger common substring.

5. Finally, the *main* function demonstrates this for the strings "ABCDEF" and "ZBCDMF". The longest common substring here is "BC", which has a length of 2.