Longest Common Substring Finder

This problem requires you to find the longest common substring of two given strings. A substring is a contiguous block of characters. In case there are multiple substrings with the same maximum length, you should return the one that appears first in the first string.

Formally, given two strings \( S_1 \) and \( S_2 \), find the substring \( X \) such that \( X \) is a substring of both \( S_1 \) and \( S_2 \), and the length of \( X \), denoted by \( |X| \), is maximized. If there are multiple solutions with the same length, choose the one with the smallest starting index in \( S_1 \).

If no common substring exists, output an empty string "".

inputFormat

The input is read from standard input (stdin) and consists of two lines. The first line contains the string ( S_1 ) and the second line contains the string ( S_2 ).

outputFormat

Print to standard output (stdout) the longest common substring. If there are multiple answers, output the one that appears first in ( S_1 ). If there is no common substring, print an empty string.## sample

abcdef
zcdemf

cde