Vamos abordar a construção e otimização de um autômato finito (AC automaton) para verificar se substirngs específicas estão presentes em uma string principal. Neste artigo, usaremos o AC automaton para resolver o problema de verificação de substrinsg de maneira eficiente.

Construção do AC Automaton

Primeiro, construímos o AC automaton com os padrões fornecidos. Cada nó no automaton representa um prefixo de algum padrão, e as transições representam as próximas letras possíveis. Além disso, cada nó tem um ponteiro fail que aponta para o nó mais próximo que é um sufixo do atual.

Implementação Inicial

A implementação inicial verifica se um prefixo de comprimento i da string t é válido, percorrendo o fail tree a partir do nó atual. Se encontrarmos um nó que é o final de um padrão e o prefixo correspondetne é válido, marcamos o prefixo atual como válido.

int query(string s) {
    int p = 0, n = s.size(), ans = 0;
    for (int i = 1; i <= n; i++) {
        p = tr[p][s[i-1] - 'a'];
        f[i] = 0;
        for (int j = p; j; j = fail[j]) {
            if (len[j] && f[i - len[j]]) {
                f[i] = 1;
                ans = i;
                break;
            }
        }
    }
    return ans;
}

Otimização

A complexidade da solução inicial é alta, levando a TLE. Para otimizar, podemos usar compressão de estados. Cada nó no fail tree armazena informações sobre os sufixos válidos em um único inteiro. Isso permite que a verificação seja feita em tempo constante.

Implementação Otimizada

Aqui está a implementação otimizada, que usa um bitset para armazenar as informações de sufixos válidos.

#include <bits/stdc++.h>
#define T 30  // número de padrões
#define N 410 // comprimento total dos padrões (número de nós)
#define M 2000010 // comprimento máximo da string principal
#define S 26  // tamanho do alfabeto
using namespace std;

int n, m, tr[N][S], fail[N], cnt;
int f[M], tlen[N];
string s[T];
queue<int> q;

void ins(string s) {
    int p = 0;
    for (char c : s) {
        int idx = c - 'a';
        if (!tr[p][idx])
            tr[p][idx] = ++cnt;
        p = tr[p][idx];
    }
    tlen[p] = 1 << (s.size() - 1); // marca o nó como final de um padrão
}

void get_fail() {
    for (int i = 0; i < 26; i++)
        if (tr[0][i]) q.push(tr[0][i]);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < 26; i++) {
            if (tr[u][i]) {
                fail[tr[u][i]] = tr[fail[u]][i];
                q.push(tr[u][i]);
                tlen[tr[u][i]] |= tlen[fail[tr[u][i]]]; // propaga as informações de sufixos válidos
            } else {
                tr[u][i] = tr[fail[u]][i];
            }
        }
    }
}

int query(string s) {
    int p = 0, x = 0, n = s.size();
    for (int i = 1; i <= n; i++) {
        p = tr[p][s[i-1] - 'a'];
        x = ((x << 1) | f[i-1]) & ((1 << 20) - 1); // atualiza o bitset
        f[i] = (x & tlen[p]) != 0; // verifica se o prefixo atual é válido
    }
    for (int i = n; i >= 0; i--)
        if (f[i]) return i;
    return -1; // caso teórico não alcançável
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        ins(s[i]);
    }
    get_fail();
    f[0] = 1; // inicializa o estado inicial
    while (m--) {
        cin >> s[0];
        cout << query(s[0]) << "\n";
    }
    return 0;
}

Com esta otimização, a complexidade temporal é reduzida para (O(n|s||\Sigma| + m|t|)), tornando a solução eficiente o suficiente para passar nos limites de tempo.