Longest Common Substring Length

You are given two strings s1 and s2. Your task is to find the length of the longest substring that appears in both s1 and s2. A substring is a contiguous sequence of characters within a string.

Let \( s1 \) have length \( m \) and \( s2 \) have length \( n \). One common approach is to use dynamic programming to compute a two-dimensional table \( dp[i][j] \), where \( dp[i][j] \) represents the length of the longest common suffix of \( s1[0\ldots i-1] \) and \( s2[0\ldots j-1] \). The recurrence is:

\[ dp[i][j] = \begin{cases} dp[i-1][j-1] + 1, & \text{if } s1[i-1] = s2[j-1] \\ 0, & \text{otherwise} \end{cases} \]

The answer is the maximum value in the \( dp \) table.

inputFormat

The input consists of two lines. The first line contains the string s1, and the second line contains the string s2.

outputFormat

Output a single integer, which is the length of the longest common substring between s1 and s2.

ABCDE
BCDFE

3