10318: CF EDU - Suffix Array - Step 5 - B. Longest Common Substring
[Creator : ]
Description
Find the longest common substring of two given strings $s$ and $t$.
Input
First line of the input has single string $s$, second — $t\ (1≤|s|,|t|≤100,000)$. Strings are made of small latin letters.
Output
Output single line — the longest common substring of strings $s$ and $t$. Output lexicographically minimal one, in case of multiple possible answers.
Sample 1 Input
bababb
zabacabba
Sample 1 Output
aba
Sample 2 Input
qrdq
rqqqrdqrqd
Sample 2 Output
qrdq
Sample 3 Input
hhhhhh
hhhhhhh
Sample 3 Output
hhhhhh
opopo
ppppopopo
opopo