El de la subpalabra común más larga P52289

Algunos problemas son tan clásicos que apenas merecen enunciado. En éste, os pedimos que calculéis cuál es la subpalabra de mayor longitud que tienen en común dos palabras dadas. En caso de haber varias, escribid la más pequeña en orden alfabético.

Entrada

La entrada consiste en diversos casos, cada uno con dos palabras no vacías $p_1$ y $p_2$ con como mucho 500 letras minúsculas.

Salida

Para cada caso, escribid la subpalabra común más larga. En caso de empate, escribid la más pequeña en orden alfabético.

Observación

Hay algoritmos muy rápidos para resolver este problema. Aquí, nos conformamos con uno que tarde tiempo proporcional a $n_1\cdot n_2$, donde $n_1$ y $n_2$ son las longitudes de $p_1$ y $p_2$.