Este artigo explora o uso de programação dinâmica (DP) em autômatos construídos, com foco no autômato KMP e na árvore de falhas para resolver problemas de contagem em strings.

Autômato KMP e Árvore de Falhas

O autômato KMP é uma estrutura que permite correspondência eficiante de padrões. A função de falha (fail) e a tabela de transição (next) são componentes chave. A árvore de falhas é construída usando a função de falha, onde cada nó representa um prefixo do padrão, e as arestas apontam para o próximo estado de falha.

Para construir o autômato KMP, calcula-se a tabela de transição next e a função de falha fail. A profundidade na árvore de falhas pode ser usada para contar o número de prefixos que são sufixos em qualquer ponto da correspondência.

DP no Autômato KMP

Em muitos problemas, é necessário contar ou otimizar aspectos relacionados a strings construídas dinamicamente. O DP pode ser realizado nos estados do autômato, onde cada estado representa o progresso na correspondência com o padrão.

Exemplo 1: Problema de Contagem Máxima

Considere o problema de construir uma string S de comprimento m de modo a maximizar o número de substrings que são prefixos de um padrão T. Isso pode ser modelado com DP no autômato KMP de T.

Design do DP: Defina dp[i][j] como a pontuação máxima após construir os primeiros i caracteres de S, estando no estado j do autômato KMP de T. A transição ao adicionar um caractere c resulta no novo estado next[j][c], e o ganho adicional é a profundidade desse estado na árvore de falhas.

Equação de Transição:

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 2000;
string padrao;
size_t transicao[MAX_N + 1][26], falha[MAX_N + 1], profundidade_falha[MAX_N + 1], n;

void construir_falha() {
    profundidade_falha[0] = 0;
    for (size_t i = 0; i < n; i++) {
        for (int k = 0; k < 26; k++) {
            if (padrao[i] - 'a' == k) {
                transicao[i][k] = i + 1;
                falha[i + 1] = (i ? transicao[falha[i]][k] : 0);
                profundidade_falha[i + 1] = profundidade_falha[falha[i + 1]] + 1;
            } else {
                transicao[i][k] = (i ? transicao[falha[i]][k] : 0);
            }
        }
    }
    for (int k = 0; k < 26; k++) {
        transicao[n][k] = (n ? transicao[falha[n]][k] : 0);
    }
}

size_t comprimento_texto;
size_t dp[MAX_N + 1][MAX_N + 1], resultado;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> padrao >> comprimento_texto;
    n = padrao.size();
    construir_falha();
    memset(dp, 0x3f, sizeof dp);
    dp[0][0] = 0;
    for (size_t i = 0; i < comprimento_texto; i++) {
        for (size_t j = 0; j <= n; j++) {
            if (dp[i][j] == 0x3f3f3f3f3f3f3f3f) continue;
            for (size_t c = 0; c < 26; c++) {
                auto novo_estado = dp[i][j] + profundidade_falha[transicao[j][c]];
                if (dp[i + 1][transicao[j][c]] == 0x3f3f3f3f3f3f3f3f || dp[i + 1][transicao[j][c]] < novo_estado) {
                    dp[i + 1][transicao[j][c]] = novo_estado;
                    if (i + 1 == comprimento_texto && resultado < dp[i + 1][transicao[j][c]]) {
                        resultado = dp[i + 1][transicao[j][c]];
                    }
                }
            }
        }
    }
    cout << resultado << endl;
    return 0;
}

Exemplo 2: Problema de String Mocha

Outro problema envolve encontrar a menor string binária t que tenha exatamente k substrings lexicograficamente menores que um padrão s e que contenha s como substring. Isso requer uma busca em largura (BFS) no espaço de estados do autômato KMP.

Design do Estado: Cada estado BFS inclui: estado atual no autômato KMP (i), contagem de substrings menores que s devido a caracteres menores (j), total de substrings menores (k), e um indicador se s já apareceu (s_in). A transição ao adicionar um caractere c atualiza esses valores usando a árvore de falhas.

Equação de Transição:

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 200;
string padrao;
size_t n, mocha_k;
size_t transicao[MAX_N + 1][2], falha[MAX_N + 1], profundidade_falha[MAX_N + 1], contador[MAX_N + 1];

void construir_falha() {
    profundidade_falha[0] = 0;
    for (size_t i = 0; i < n; i++) {
        for (int k = 0; k <= 1; k++) {
            if (padrao[i] - '0' == k) {
                transicao[i][k] = i + 1;
                falha[i + 1] = (i ? transicao[falha[i]][k] : 0);
                profundidade_falha[i + 1] = profundidade_falha[falha[i + 1]] + 1;
            } else {
                transicao[i][k] = (i ? transicao[falha[i]][k] : 0);
            }
        }
    }
    for (int k = 0; k <= 1; k++) {
        transicao[n][k] = (n ? transicao[falha[n]][k] : 0);
    }
    for (size_t i = 0; i <= n; i++) {
        contador[i] = (i ? contador[falha[i]] : 0) + (i < n ? padrao[i] == '1' : 0);
    }
}

struct EstadoBFS {
    size_t i, j, k;
    bool s_in;
    size_t anterior;
    bool ultimo_c = 0;
    EstadoBFS(size_t i_ = 0, size_t j_ = 0, size_t k_ = 0, bool s_in_ = 0, size_t anterior_ = 0, bool ultimo_c_ = 0)
        : i(i_), j(j_), k(k_), s_in(s_in_), anterior(anterior_), ultimo_c(ultimo_c_) {}
} estados[1600001];

bool visitado[MAX_N + 1][MAX_N + 1][MAX_N + 1][2];
size_t total_estados = 0;

int resolver() {
    memset(visitado, 0, sizeof visitado);
    cin >> n >> mocha_k >> padrao;
    construir_falha();
    estados[total_estados = 0] = EstadoBFS(0, 0, 0, 0, 0, 0);
    queue<size_t> fila;
    fila.push(0);
    size_t objetivo = 0;
    while (!fila.empty()) {
        auto id = fila.front(); fila.pop();
        if (estados[id].s_in && estados[id].k == mocha_k) {
            objetivo = id;
            break;
        }
        for (int c = 0; c <= 1; c++) {
            const auto& [i, j, k, s_in, anterior, ultimo_c] = estados[id];
            EstadoBFS novo(transicao[i][c], j + (c == 0 ? contador[i] : 0));
            novo.k = k + novo.j + (profundidade_falha[novo.i] - (novo.i == n));
            novo.s_in = (s_in | (novo.i == n));
            novo.anterior = id;
            novo.ultimo_c = c;
            if (visitado[novo.i][novo.j][novo.k][s_in] || novo.k > mocha_k) continue;
            visitado[novo.i][novo.j][novo.k][s_in] = 1;
            estados[++total_estados] = novo;
            fila.push(total_estados);
        }
    }
    string resposta;
    for (; objetivo; objetivo = estados[objetivo].anterior) {
        resposta += (estados[objetivo].ultimo_c ? '1' : '0');
    }
    reverse(resposta.begin(), resposta.end());
    if (!resposta.size()) resposta = "Impossível";
    cout << resposta << endl;
    return 0;
}

int main() {
    int casos, testes;
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> casos >> testes;
    while (testes--) resolver();
    return 0;
}

A complexidade de tempo é aproximadamente O(nk^{3/2}), onde n é o comprimento do padrão e k é o limite de contagem.

Este artigo demonstra como a combinação de autômatos e DP pode resolver problemas complexos de strings, enfatizando a importância de entender estruturas fundamentais como o autômato KMP e a árvore de falhas.