Explain the concept of optimal substructure in the context of the Longest Common Substring problem.

In the context of the Longest Common Substring problem, the concept of optimal substructure refers to the property that the optimal solution to the problem can be constructed from the optimal solutions of its subproblems.

In the Longest Common Substring problem, we are given two strings and we need to find the longest substring that is common to both strings. To solve this problem using dynamic programming, we can break it down into smaller subproblems.

Let's consider two strings, string A of length m and string B of length n. We can define a table, let's call it LCS, of size (m+1) x (n+1), where LCS[i][j] represents the length of the longest common substring ending at the i-th character of string A and the j-th character of string B.

The optimal substructure property in this problem can be observed as follows: the length of the longest common substring ending at the i-th character of string A and the j-th character of string B can be determined by the length of the longest common substring ending at the (i-1)-th character of string A and the (j-1)-th character of string B, if the i-th and j-th characters of the strings are the same. Otherwise, the length of the longest common substring ending at the i-th character of string A and the j-th character of string B will be 0.

Using this observation, we can fill the LCS table iteratively. Starting from the first character of both strings, we compare each pair of characters. If they are the same, we increment the value in the LCS table by 1, considering the length of the longest common substring ending at the (i-1)-th character of string A and the (j-1)-th character of string B. If they are different, we set the value in the LCS table to 0.

After filling the entire LCS table, the maximum value in the table represents the length of the longest common substring. We can then backtrack from this maximum value to reconstruct the actual substring.

In summary, the optimal substructure property in the Longest Common Substring problem allows us to break down the problem into smaller subproblems and construct the optimal solution by combining the solutions of these subproblems.