Escrito por Leonardo Paes.
Conhecimento prévio necessário:
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:
- Não utilizar nenhuma operação e supor que esse caractere não está em $$t$$: $$solve(pos+1, cnt, op)$$.
- Seja $$t_0 = t_1$$.
- 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: