\documentclass{maratona}

\begin{document}
\begin{ProblemaAutor}{}{Maior Subsequência Comum}{1}{256}{Arthur Andrade D'Olival}

O objetivo deste problema é determinar o comprimento da \textbf{maior subsequência comum} (Longest Common Subsequence - LCS) entre duas strings fornecidas.
Uma \textit{subsequência} é uma sequência que pode ser obtida a partir de uma string original removendo-se zero ou mais caracteres, sem alterar a ordem relativa dos caracteres restantes.
Dadas duas strings \( s_1 \) e \( s_2 \), deseja-se determinar \textbf{o comprimento da maior subsequência comum} e também \textbf{uma subsequência comum de comprimento máximo} presente em ambas.

\Entrada

A entrada é composta por duas linhas. 
Na primeira linha, há dois inteiros \( n \) e \( m \) (\( 1 \leq n, m \leq 1000 \)), representando respectivamente os tamanhos das strings \( s_1 \) e \( s_2 \).
Na segunda linha, há duas strings \( s_1 \) e \( s_2 \), cada uma composta apenas por letras minúsculas do alfabeto, com tamanhos \( n \) e \( m \), respectivamente.

\Saida

A saída consiste em duas linhas. 
Na primeira linha, deve ser impresso o comprimento da maior subsequência comum.
Na segunda linha, deve ser impressa uma subsequência comum de comprimento máximo.

\ExemploEntrada

\begin{Exemplo}
\texttt{5~3} & \texttt{3}\\
\texttt{abcde~ace} & \texttt{ace}\\
\rowcolor{gray!20}\texttt{3~3} & \texttt{3}\\
\rowcolor{gray!20}\texttt{abc~abc} & \texttt{abc}\\
\texttt{3~3} & \texttt{0}\\
\texttt{abc~hhh} & \texttt{}\\
\end{Exemplo}



\Notas

Para as strings \( s_1 = abcde \) e \( s_2 = ace \), a maior subsequência comum é "ace", que possui tamanho 3.

Para \( s_1 = abc \) e \( s_2 = abc \), ambas as strings são idênticas, logo a maior subsequência comum é "abc", que possui tamanho 3.

Para \( s_1 = abc \) e \( s_2 = hhh \), não há caracteres em comum, e portanto a maior subsequência comum é a palavra vazia, que tem tamanho 0.
\end{ProblemaAutor}
\end{document}