En el libro "Un libro completo para Olimpiadas de Informática - Parte Mejora", encontré este problema como ejercicio práctico del capítulo sobre árboles Trie. Decidí resolverlo utilizando la estructura de Trie. Se dice que la solución correcta para este problema es el autómata AC, ya que otros algoritmos pueden ser ineficientes con datos grandes. Sin embargo, los datos no eran lo suficientemente exigentes, así que finalmente logré resolverlo.

Descripción

Se proporcionan \(n\) vocablos y \(m\) oraciones. Cada oración consiste en una secuencia continua de vocablos, y cada vocablo está compuesto por una secuencia continua de caracteres. Un vocablo se considera comprendido únicamente si puede ser identificado completamente, es decir, pertenece a uno de los vocablos dados. Para una oración, un vocablo solo puede comenzar a ser reconocido si todos los vocablos anteriores en la oración ya han sido comprendidos. Para cada oración, se solicita determinar la posición final del último vocablo que puede ser comprendido.

Solución

Aquí explicaré cómo utilizar un árbol Trie para resolver este problema. Primero, consideremos el ejemplo:

4 3 
is
name
what
your
whatisyourname
whatisyouname
whaisyourname

Estos son los vocablos y oraciones proporcionados. Debemos pensar en cómo identificar cada vocablo en las oraciones desde el principio. Basado en los principios de los árboles Trie, podemos construir un árbol donde cada vocablo dado es una rama y cada carácter actúa como condición de transición. Específicamente, como se muestra en el diagrama:

Comenzamos desde el nodo raíz y recorremos hacia abajo. Cada vez que comprendemos un vocablo, actualizamos un contador. Si encontramos un error durante el recorrido, devolvemos la respuesta inmediatamente. Si llegamos a un nodo hoja sin encontrar errores, regresamos al nodo raíz para buscar el siguiente vocablo, hasta que ocurra un error o toda la oración haya sido comprendida. De esta manera, podemos encontrar lentamente la posición final que puede ser comprendida en cada oración.

Sobre esta base, mantenemos dos mapas: uno para registrar si una oración ya ha sido procesada, y otro para almacenar la posición final alcanzada en esa oración. La razón es que en ciertas situaciones, los mismos pasos de cálculo pueden repetirse muchas veces, pero usando estos mapas podemos resolver este problema, similar a la memorización en recursión. Cuando el primer mapa indica que la oración ya ha sido procesada, podemos usar el segundo mapa para obtener directamente la posición final correspondiente, evitando así volver a procesar la oración. Esto hace que este enfoque de complejidad temporal deficiente sea ligeramente más rápido.

Otros aspectos

Claramente, este es un enfoque de fuerza bruta, una solución improvisada. Sin embargo, el árbol Trie en sí no es la solución correcta para este problema. Si funciona, es porque los datos no son suficientemente exigentes. En respeto a los autores de "Un libro completo para Olimpiadas de Informática - Parte Mejora", utilicé el método especificado. En cuanto a la solución correcta para este problema, el autómata AC, no lo sé, jeje.

Código

#include<map>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 200010
#define LL long long
#define uLL unsigned long long

using namespace std;

int n,m,resultado;
char vocablo[25],oracion[maxn];
map<string,int> Obtener;
map<string,bool> Verificar;

inline int leer(){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
    return s*w;
}

struct ArbolTrie{
    int Siguiente[maxn][25],contador;
    bool marca[maxn],visitado[maxn];
    void Insertar(char *s){
        int p=0,longitud=strlen(s+1);
        for(int i=1;i<=longitud;i++){
            int c=s[i]-'a';    
            if(!Siguiente[p][c]) Siguiente[p][c]=++contador;
                p=Siguiente[p][c];
        }
        marca[p]=1;
    }
    
    int Buscar(char *s){
        int p=0,longitud=strlen(s+1);
        if(Verificar[s+1]) return Obtener[s+1];
        memset(visitado,false,sizeof visitado);visitado[0]=true;
        for(int i=0;i<=longitud;i++){
            if(!visitado[i]) continue;contador=i;
            for(int j=i+1;j<=longitud;j++){
                int c=s[j]-'a';
                p=Siguiente[p][c];if(!p) break;
                if(marca[p]) visitado[j]=true;
            }
        }
        Verificar[s+1]=true;Obtener[s+1]=contador;
        return contador;
    }
}Trie;

int main(){
    n=leer();m=leer();
    for(int i=1;i<=n;i++){
        scanf("%s",vocablo+1);
        Trie.Insertar(vocablo);
    }
    for(int i=1;i<=m;i++){
        scanf("%s",oracion+1);
        printf("%d\n",Trie.Buscar(oracion));
    }
    return 0;
}