फ़ज़ी मैचिंग (Fuzzy Matching)
कल्पना कीजिए कि आप Google के शुरुआती इंजीनियरों में से एक हैं, और आपको Google Search में ऐसा फ़ीचर लागू करना है जो यह जांचे कि उपयोगकर्ता द्वारा दिया गया इनपुट डेटाबेस में मौजूद है या नहीं।
शुरुआत में, आप सर्च एल्गोरिथ्म पर काम कर रहे हैं और एक परीक्षण डेटासेट पर प्रयोग कर रहे हैं, जिसमें केवल तीन लोअरकेस अक्षर
a, b और c शामिल हैं।
डेटाबेस में
n स्ट्रिंग्स हैं, और आपको k क्वेरी दी गई हैं। आप सर्च इंजन को तेज़ और कम से कम त्रुटिपूर्ण बनाना चाहते हैं, इसलिए आपने तय किया है कि अधिकतम 1 गलत अक्षर की अनुमति दी जाएगी।हर क्वेरी स्ट्रिंग के लिए, प्रोग्राम को चेक करना चाहिए कि वह स्ट्रिंग डेटाबेस में मौजूद है या नहीं, बशर्ते उसमें अधिकतम एक अक्षर की ग़लती की अनुमति हो (कोई अक्षर जोड़ा या हटाया नहीं जाएगा)।
इनपुट
इनपुट की पहली पंक्ति में एक एकल पूर्णांक
n (1 ≤ n ≤ 100 000) दिया होता है।अगली
n पंक्तियों में डेटाबेस में मौजूद स्ट्रिंग्स होती हैं। यह निश्चित किया जाता है कि डेटाबेस में मौजूद सभी स्ट्रिंग्स की कुल लंबाई 100 000 से ज़्यादा नहीं है।इसके बाद की पहली पंक्ति में क्वेरी की संख्या
k (1 ≤ k ≤ 100 000) दी होती है।अगली
k पंक्तियों में क्वेरी स्ट्रिंग्स होती हैं। यह निश्चित किया जाता है कि सभी क्वेरी स्ट्रिंग्स की कुल लंबाई 100 000 से ज़्यादा नहीं है।आउटपुट
हर क्वेरी स्ट्रिंग के लिए, अगर वह डेटाबेस में मौजूद है (अधिकतम 1 ग़लत अक्षर की अनुमति के साथ), तो प्रोग्राम
Yes प्रिंट करे, अन्यथा No।उदाहरण
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