Longest Common Substring

Problem Description:

Given two strings s1 and s2, your task is to find the longest common substring between them. A substring is a contiguous sequence of characters within a string. If there is more than one longest common substring, output the one that occurs first in s1. If there is no common substring, output an empty string.

The solution is expected to use a dynamic programming approach. The recurrence relation used in the algorithm can be expressed as:

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

where dp[i][j] represents the length of the longest common suffix of the substrings ending at positions i-1 in s1 and j-1 in s2. The answer is the substring of s1 corresponding to the maximum value found in the dp table.

inputFormat

The input is given via standard input (stdin) and consists of two lines:

Line 1: A non-empty string s1 Line 2: A non-empty string s2

Each string may contain any characters.

outputFormat

Output via standard output (stdout) a single line containing the longest common substring between s1 and s2. If no common substring exists, output an empty string.## sample

abcdef
zcdemf

cde