Fuzzy համընկնում
Պատկերացրեք, որ դուք Google-ի առաջին ինժեներներից եք, և պետք է անհրաժեշտ գործառույթ մշակեք Google Search-ում՝ ստուգելու համար, արդյոք օգտատիրոջ մուտքագրած տեքստը գտնվում է տվյալների բազայում, թե ոչ:
Քանի որ դեռ նոր եք սկսում աշխատել որոնման ալգորիթմի վրա, դուք փորձեր եք կատարում մի պարզ փորձնական տվյալների բազայի վրա, որտեղ բառերը կազմված են միայն
a, b և c փոքրատառատառերի համադրությունից:
Դուք ունեք
n քանակով տողեր տվյալների բազայում, և տրված են k հարցումներ (query)։ Ցանկանում եք, որ որոնողական համակարգը լինի թե՛ արագագործություն ապահովող, թե՛ փոքր սխալների հանդեպ հանդուրժող, ուստի որոշում եք թույլ տալ ոչ ավելի, քան 1 սխալագրված նիշ:Ե每 հարցման տողի համար ծրագիրը պետք է ստուգի, թե արդյոք հարցման տողը առկա է տվյալների բազայում՝ թույլատրելով ոչ ավելի, քան մեկ սխալագրված նիշ (առանց նիշեր ավելացնելու կամ հեռացնելու):
Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ 100 000)։Հաջորդ
n տողերում տրված են տվյալների բազայում առկա տողերը ։ Համոզված եք, որ տվյալների բազայի բոլոր տողերի երկարությունների գումարը չի գերազանցում 100 000-ը։Այնուհետև Մուտքի առաջին տողում (հաջորդաբար) տրված է մեկ ամբողջ թիվ
k (1 ≤ k ≤ 100 000), որը ցույց է տալիս հարցումների քանակը։Այդուհետև հաջորդ
k տողերում տրված են հարցման տողերը ։ Նույնպես երաշխավորված է, որ հարցման տողերի երկարությունների ընդհանուր գումարը չի անցնում 100 000-ը։Ելք
Ե每 հարցման տողի համար ծրագիրը պետք է տպի
Yes, եթե տվյալ հարցման տողը (թույլատրելով ոչ ավելի, քան 1 սխալագրված նիշ) գտնվում է տվյալների բազայում, հակառակ դեպքում՝ No:Օրինակներ
Մուտք | Ելք |
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