Para abordar este problema, el objetivo es calcular la frecuencia de aparición de cada palabra proporcionada dentro del conjunto completo de cadenas. Dado que necesitamos manejar múltiples patrones simultáneamente, la estructura de datos ideal es el Autómata Aho-Corasick.

El procedimiento comienza construyendo un trie con todas las cadenas de entrada. Durante la fase de inserción, mantenemos un contador en cada nodo que registra cuántas veces se atraviesa dicho nodo. Esto representa inicialmente la cantidad de veces que aparece el prefijo correspondiente a ese nodo.

La lógica central se basa en los punteros de fallo (fail pointers). Estos puntores forman un árbol de fallos donde la relación padre-hijo indica una relación de sufijo. Específicamente, si un nodo v pertenece al subárbol de un nodo u en el árbol de fallos, la cadena representada por u es un sufijo de la cadena representada por v. Por consiguiente, la cantidad total de apariciones de una palabra que termina en el nodo u es igual a la suma de los contadores de todoss los nodos en el subárbol de u.

Para acumular estos valores correctamente desde las hojas hacia la raíz del árbol de fallos, existen dos enfoques principales:

1. Ordenamiento Topológico: Se calculan los grados de entrada de cada nodo en el árbol de fallos y se procesan aquellos con grado cero, propagando los conteos hacia sus padres.
2. Orden BFS Inverso: Dado que los punteros de fallo se generan mediante una búsqueda en anchura (BFS), el orden de visita garantiza que los padres en el árbol de fallos aparecen antes que los hijos. Iterar la cola de BFS en orden inverso proporciona automáticamente un orden topológico válido, eliminando la necesidad de calcular grados explícitamente.

Implementación con Ordenamiento Topológico

Esta versión utiliza un cálculo explícito de grados de entrada para gestionar la propagación de los conteos de ocurrencia.

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

using namespace std;

const int MAX_NODES = 1000005;
const int ALPHABET = 26;
const int MAX_WORDS = 205;

int trie[MAX_NODES][ALPHABET];
int failureLink[MAX_NODES];
int occurrenceCount[MAX_NODES];
int wordEndNode[MAX_WORDS];
int inDegree[MAX_NODES];
int nodeCounter = 0;
int n;

void insertWord(const string& s, int id) {
    int current = 0;
    for (char c : s) {
        int idx = c - 'a';
        if (!trie[current][idx]) {
            trie[current][idx] = ++nodeCounter;
        }
        current = trie[current][idx];
        occurrenceCount[current]++;
    }
    wordEndNode[id] = current;
}

void buildAutomaton() {
    queue<int> q;
    for (int i = 0; i < ALPHABET; ++i) {
        if (trie[0][i]) {
            q.push(trie[0][i]);
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int i = 0; i < ALPHABET; ++i) {
            if (trie[u][i]) {
                failureLink[trie[u][i]] = trie[failureLink[u]][i];
                inDegree[failureLink[trie[u][i]]]++;
                q.push(trie[u][i]);
            } else {
                trie[u][i] = trie[failureLink[u]][i];
            }
        }
    }
}

void propagateCounts() {
    queue<int> q;
    for (int i = 1; i <= nodeCounter; ++i) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        int f = failureLink[u];
        if (f != 0) {
            occurrenceCount[f] += occurrenceCount[u];
            inDegree[f]--;
            if (inDegree[f] == 0) {
                q.push(f);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n)) return 0;

    for (int i = 1; i <= n; ++i) {
        string s;
        cin >> s;
        insertWord(s, i);
    }

    buildAutomaton();
    propagateCounts();

    for (int i = 1; i <= n; ++i) {
        cout << occurrenceCount[wordEndNode[i]] << "\n";
    }

    return 0;
}

Implementación Optimizada con Orden BFS Inverso

Esta alternativa mejora la eficiancia evitando el cálculo de grados. Utiliza un array para almacenar el orden de visita BFS y lo recorre en sentido inverso para actualizar los acumuladores.

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

using namespace std;

#define MAX_N 1000010
#define MAX_M 210
#define SIGMA 26

int transition[MAX_N][SIGMA];
int failPtr[MAX_N];
int countPass[MAX_N];
int endPos[MAX_M];
int bfsQueue[MAX_N];
int totalNodes = 0;
int wordCount = 0;

void addPattern(string& txt, int index) {
    int node = 0;
    for (char ch : txt) {
        int c = ch - 'a';
        if (!transition[node][c]) {
            transition[node][c] = ++totalNodes;
        }
        node = transition[node][c];
        countPass[node]++;
    }
    endPos[index] = node;
}

void constructFailureLinks() {
    int head = 0, tail = 0;
    for (int i = 0; i < SIGMA; ++i) {
        if (transition[0][i]) {
            bfsQueue[++tail] = transition[0][i];
        }
    }

    while (head < tail) {
        int curr = bfsQueue[++head];
        for (int i = 0; i < SIGMA; ++i) {
            if (transition[curr][i]) {
                failPtr[transition[curr][i]] = transition[failPtr[curr]][i];
                bfsQueue[++tail] = transition[curr][i];
            } else {
                transition[curr][i] = transition[failPtr[curr]][i];
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> wordCount;
    for (int i = 1; i <= wordCount; ++i) {
        string temp;
        cin >> temp;
        addPattern(temp, i);
    }

    constructFailureLinks();

    for (int i = totalNodes; i > 0; --i) {
        int u = bfsQueue[i];
        countPass[failPtr[u]] += countPass[u];
    }

    for (int i = 1; i <= wordCount; ++i) {
        cout << countPass[endPos[i]] << "\n";
    }

    return 0;
}