O cálculo do substring e subsequência comuns máximos entre duas strings é uma tarefa comum em ciência da computação, frequentemente resolvida através de programação dinâmica. Embora ambas as abordagens sejam semelhantes, as equações de recorrência utilziadas diferem.

Cálculo do Substring Comum Máximo:

#include <iostream>
#include <vector>
#include <string>

std::string maiorSubstringComum(const std::string& textoA, const std::string& textoB) {
    if (textoA.empty() || textoB.empty()) {
        return "";
    }

    int tamanhoMaximo = 0, posicaoFim = 0;
    std::vector<:vector>> tabela(textoA.size(), std::vector<int>(textoB.size(), 0));

    for (size_t i = 0; i < textoA.size(); ++i) {
        for (size_t j = 0; j < textoB.size(); ++j) {
            if (textoA[i] == textoB[j]) {
                if (i == 0 || j == 0) {
                    tabela[i][j] = 1;
                } else {
                    tabela[i][j] = tabela[i - 1][j - 1] + 1;
                }
                if (tabela[i][j] > tamanhoMaximo) {
                    tamanhoMaximo = tabela[i][j];
                    posicaoFim = i;
                }
            }
        }
    }
    return textoA.substr(posicaoFim - tamanhoMaximo + 1, tamanhoMaximo);
}

int main() {
    std::string entrada, strUm, strDois;
    while (std::getline(std::cin, entrada)) {
        if (strUm.empty()) {
            strUm = entrada;
        } else if (strDois.empty()) {
            strDois = entrada;
        }
        if (!strUm.empty() && !strDois.empty()) {
            std::cout << maiorSubstringComum(strUm, strDois) << std::endl;
            strUm.clear();
            strDois.clear();
        }
        entrada.clear();
    }
}</int></:vector>

Cálculo da Subsequência Comum Máxima:

A subsequência comum máxima difere do substring comum máximo em que os caracteres da subsequência não precisam ser consecutivos na string original.

#include <iostream>
#include <vector>
#include <string>

int comprimentoSubsequenciaComum(const std::string& seqA, const std::string& seqB, std::vector<std::vector<int>>& matriz, std::vector<std::vector<int>>& direcao) {
    for (size_t i = 1; i <= seqA.size(); ++i) {
        for (size_t j = 1; j <= seqB.size(); ++j) {
            if (seqA[i - 1] == seqB[j - 1]) {
                matriz[i][j] = matriz[i - 1][j - 1] + 1;
                direcao[i][j] = 1;
            } else if (matriz[i - 1][j] > matriz[i][j - 1]) {
                matriz[i][j] = matriz[i - 1][j];
                direcao[i][j] = 2;
            } else {
                matriz[i][j] = matriz[i][j - 1];
                direcao[i][j] = 3;
            }
        }
    }
    return matriz[seqA.size()][seqB.size()];
}

void exibirSubsequenciaComum(const std::vector<std::vector<int>>& direcao, const std::string& seqA, size_t linha, size_t coluna) {
    if (linha == 0 || coluna == 0) {
        return;
    }
    if (direcao[linha][coluna] == 1) {
        exibirSubsequenciaComum(direcao, seqA, linha - 1, coluna - 1);
        std::cout << seqA[linha - 1];
    } else if (direcao[linha][coluna] == 2) {
        exibirSubsequenciaComum(direcao, seqA, linha - 1, coluna);
    } else {
        exibirSubsequenciaComum(direcao, seqA, linha, coluna - 1);
    }
}

int main() {
    std::string linhaEntrada;
    std::getline(std::cin, linhaEntrada);
    std::stringstream separador(linhaEntrada);
    std::string sequenciaA, sequenciaB;
    separador >> sequenciaA >> sequenciaB;
    std::vector<std::vector<int>> matriz(sequenciaA.size() + 1, std::vector<int>(sequenciaB.size() + 1));
    std::vector<std::vector<int>> direcao(sequenciaA.size() + 1, std::vector<int>(sequenciaB.size() + 1));
    std::cout << comprimentoSubsequenciaComum(sequenciaA, sequenciaB, matriz, direcao) << std::endl;
    exibirSubsequenciaComum(direcao, sequenciaA, sequenciaA.size(), sequenciaB.size());
    return 0;
}