Fuzzy Matching (Coincidencia Difusa)
Imagínate que eres uno de los primeros ingenieros de Google y necesitas implementar una función en Google Search que verifique si la entrada del usuario se encuentra en la base de datos o no.
Como apenas estás comenzando a trabajar en el algoritmo de búsqueda, estás probando con un conjunto de datos que solo contiene texto con 3 letras minúsculas:
a, b y c.
Hay
n cadenas en la base de datos y se te dan k consultas. Deseas que el motor de búsqueda sea eficiente y tolerante a errores, así que decides permitir como máximo 1 carácter mal escrito.Para cada cadena de consulta, el programa debe verificar si la cadena de consulta se encuentra en la base de datos, permitiendo como máximo un carácter con error (sin agregar ni eliminar caracteres).
Entrada
La primera línea de la entrada contiene un solo entero
n (1 ≤ n ≤ 100 000).Las siguientes
n líneas contienen las cadenas presentes en la base de datos . Se garantiza que la suma de las longitudes de las cadenas en la base de datos no excede 100 000.La primera línea de la entrada contiene un solo entero
k (1 ≤ k ≤ 100 000), el número de consultas.Las siguientes
k líneas contienen las cadenas de consulta . Se garantiza que la suma de las longitudes de las cadenas de consulta no excede 100 000.Salida
Para cada una de las cadenas de consulta, el programa debe imprimir
Yes si existe en la base de datos y No en caso contrario, permitiendo como máximo un carácter mal escrito.Ejemplos
Input | Entrada |
2
aaabccc
aaaaaac
4
aaabccc
aabaccc
aaaaaab
aaaaaaaab | 2
aaabccc
aaaaaac
4
aaabccc
aabaccc
aaaaaab
aaaaaaaab |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB