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.