Fuzzy Matching
Imagine you are one of the earliest engineers at Google, and you need to implement a feature on Google Search that checks whether the user input is present in the database or not.
As you’re just starting to work on the search algorithm, you’re playing with a test dataset that only contains text with 3 lowercase letters
a, b, and c.
There are
n strings in the database and you are given k queries. You want to make the search engine both performant and fault-tolerant, so you’ve decided to allow at most 1 misspelled letter.For each query string, the program should check if the query string is present in the database while allowing at most one misspelled character (no adding or removing characters).
Input
The first line of the input contains a single integer
n (1 ≤ n ≤ 100 000).The next
n lines contain the strings present in the database The first line of the input contains a single integer
k (1 ≤ k ≤ 100 000) the number of queries.The next
k lines contain the query strings Output
For each of the query strings, the program should print
Yes if it exists in the database and No otherwise, while allowing for at most 1 misspelled letter.Examples
Input | Output |
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