Solução Informática - Nivel Avançado - Semana 21

Escrito por Leonardo Paes.

Conhecimento prévio necessário:

• DP

Para resolvermos esse problema, iremos utilizar Programação Dinâmica. Seja $dp[pos][cnt][op] =$ maior quantidade de ocorrências de $t$ em $s$ no sufixo de $s$ que começa na posição $pos$, tendo $cnt$ caracteres no prefixo de $s$ anterior a $pos$ que são iguais a $t_0$ e podendo utilizar $op$ operações descritas no enunciado (substituir um caractere de $s$).

Temos alguns casos a considerar:

1. Não utilizar nenhuma operação e supor que esse caractere não está em $t$: $solve(pos+1, cnt, op)$.
2. Seja $t_0 = t_1$.
3. Seja $t_0 \neq t_1$.

Para entedermos as transições utilizadas nos casos $2$ e $3$, basta observarmos o código abaixo.

Código de exemplo: