Longest Common Substring

Given two strings s₁ and s₂, find the longest common substring shared between them. A common substring is a sequence of characters that appears in the same order in both strings and is contiguous.

If there is more than one substring with the maximum length, you may return any one of them.

The solution should read input from standard input (stdin) and produce the result to standard output (stdout).

Note: The algorithm should be efficient enough for moderately sized inputs.

The formula for the dynamic programming recurrence is:

\[ LCSuff(i,j)=\begin{cases} LCSuff(i-1,j-1)+1, &\text{if } s_1[i-1]=s_2[j-1]\\ 0, &\text{otherwise} \end{cases} \]

where LCSuff(i,j) represents the length of the longest common suffix of s₁[0 \ldots i-1] and s₂[0 \ldots j-1].

inputFormat

The input consists of two lines. The first line contains the string s₁ and the second line contains the string s₂.

outputFormat

Output the longest common substring between the two given strings. If no common substring exists, output an empty string.

substring
substring

substring