The one of the greatest common subword P52289


Statement
 

pdf   zip

thehtml

Some problems are so classic that barely need a statement. For this one, we ask you to compute the longest subword that two given words have in common. In case of a tie, print the smallest one in alphabetical order.

Input

Input consists of several cases, each with two non-empty words w1 and w2 made up of at most 500 lowercase letters.

Output

For every case, print the longest common subword. In case of a tie, print the smallest one in alphabetical order.

Observation

There are very fast algorithms to solve this problem. Here, we settle for one that takes time proportional to n1· n2, where n1 and n2 are the lengths of w1 and w2.

Public test cases

  • Input

    pseudopseudohypoparathyroidism
floccinaucinihilipilification

supercalifragilisticexpialidocious
sipircilifrigilisticixpiilidiciiis

supercalifragilisticexpialidocious
zzz

abczzzcdazzzaba
abcxxxcdaxxxaba

    Output

    at
gilistic

aba
    • Information
    Author
    Omer Giménez
    Language
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++ Python