T05 Número de LCSs
Sejam \(s\) e $t$ duas palavras sobre um alfabeto dado. Denotemos por $\ell(s, t)$ o comprimento das LCSs de $s$ e $t$ e por $n(s, t)$ o número de tais LCSs. Por exemplo, se $s=\mathit{abba}$ e $t=\mathit{baab}$, então $\ell(s, t)=2$ e $n(s, t)=4$. De fato, podemos verificar que $\mathit{aa}$, $\mathit{ab}$, $\mathit{ba}$ e $\mathit{bb}$ são todas as LCSs de $s$ e $t$. Se $s=\mathit{abbaa}$ e $\mathit{baabb}$, então $\ell(s, t)=3$ e $n(s, t)=2$ (as LCSs são $\mathit{abb}$ e $\mathit{baa}$).
Sejam $M$ o comprimento de $s$ e $N$ o comprimento de $t$. Seja $s'=s[1,M)$ o sufixo de $s$ de comprimento $M-1$ e seja $t'=t[1,N)$ o sufixo de $t$ de comprimento $N-1$. Sejam $s_0=s[0]$ e $t_0=t[0]$ as primeiras letras de $s$ e $t$. Neste exercício, você deve encontrar uma forma de expressar $n(s, t)$ em função de $n(s',t')$, $n(s,t')$ e $n(s',t)$.
Por exemplo, no caso em que $s_0=t_0$, vale que $n(s,t)=n(s',t')$. Um bom exercício é verificar esta afirmação.
Considere agora o caso em que $s_0\neq t_0$. Determine uma forma de expressar $n(s, t)$ em função de $n(s',t')$, $n(s,t')$ e $n(s',t)$ neste caso. Justifique sua resposta.
Observação. A expressão para $n(s, t)$ que você encontrará para o caso em que $s_0\neq t_0$ e a expressão acima para o caso em que $s_0=t_0$ devem, em conjunto, sugerir um bom algoritmo para se determinar $n(s, t)$ (basicamente tão bom quanto aquele que conhecemos para determinar $\ell(s, t)$).