Fuzzy Matching
Imagine que é um dos primeiros engenheiros no Google e precisa de implementar uma funcionalidade no Google Search que verifique se o input do utilizador está presente na base de dados ou não.
Como está apenas a começar a trabalhar no algoritmo de pesquisa, está a experimentar um conjunto de dados de teste que só contém texto com as letras minúsculas
a, b e c.
Existem
n strings na base de dados e recebe k consultas (queries). Pretende que o motor de pesquisa seja tanto eficiente como tolerante a falhas, por isso decidiu permitir, no máximo, 1 letra incorreta.Para cada query string, o programa deve verificar se esta existe na base de dados, permitindo até 1 carácter mal escrito (sem adicionar ou remover caracteres).
Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ 100 000).As
n linhas seguintes contêm as strings presentes na base de dados . É garantido que a soma dos comprimentos das strings na base de dados não excede 100 000.A primeira linha da entrada contém um único inteiro
k (1 ≤ k ≤ 100 000), que representa o número de consultas.As
k linhas seguintes contêm as strings de pesquisa . É garantido que a soma dos comprimentos das strings de pesquisa não excede 100 000.Saída
Para cada uma das query strings, o programa deve imprimir
Yes se ela existir na base de dados e No caso contrário, permitindo até 1 letra mal escrita.Exemplos
Entrada | Saída |
2
aaabccc
aaaaaac
4
aaabccc
aabaccc
aaaaaab
aaaaaaaab | Yes
No
Yes
No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB