T03 Junção: cota inferior
Seja \(s\) um string. Uma subsequência de $s$ é qualquer string que pode ser obtido a partir de $s$ removendo-se alguns caracteres de $s$. Por exemplo, se $s=abbaba$, os strings $aaa$, e $aba$ e $b$ são subsequências de $s$. Note que, para qualquer $s$, tanto $s$ como o string vazio são subsequências de $s$.
Uma junção, ou join, de $s$ e $t$ é um string $u$ tal que ambos $s$ e $t$ são subsequências de $u$. Por exemplo, a concatenação $st$ de $s$ e $t$ é uma junção de $s$ e $t$. Dizemos que uma junção é minimal se ela tem comprimento menor possível. Seja $L(s,t)$ tal comprimento. Seja $\ell(s,t)$ o comprimento da subsequência comum mais longa de $s$ e $t$. Prove que \( L(s,t)\geq|s|+|t|-\ell(s,t), \) onde $|s|$ e $|t|$ são os comprimentos de $s$ e $t$.
Observação. No Exercício E07 Junção, pede-se que você implemente um algoritmo que, dados $s$ e $t$, calcula uma junção de $s$ e $t$ com comprimento $|s|+|t|-\ell(s,t)$. Assim, segue deste exercício e do E07 que $L(s,t)=|s|+|t|-\ell(s,t)$.